Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Ask HN: Favorite pointer tricks in C?

news.ycombinator.com

Post reply on HN
Print view View original

21–30 of 81 posts

Re: Ask HN: Favorite pointer tricks in C?

#21

Post by dlsspy »

Regarding function pointer arrays, I'm doing something in labrea (http://github.com/dustin/labrea) where I need to make what is effectively an FFI call from C to C where I know the number of arguments, and their types, but I have them in the form of an array of unions.

For example, if I need to call read, it's basically an invocation of a function with a 4 byte, 8 byte, and then 4 byte argument (on a 64-bit system). I have a union argument type that represents 32-bit and 64-bit parameter types at the same time. I make a call like this:

    rv = abstractInvoke(&fun, args);
which, depending on arity of fun, invokes something like this (auto-generated):

    rv = abstractInvoke(fun, args[0], args[1], args[2]);
That three-arg function looks roughly like this (calling my argument type ``a_t'' to abbreviate):

    a_t abstractInvoke(struct ftype *fun, a_t a0, a_t a1, a_t a2) {
        static a_t (*allfuns[])(const void*, a_t a0, a_t a1, a_t a2) = {
            invoke_3_4_444, // 0
            invoke_3_8_444, // 1
            invoke_3_4_448, // 2
            invoke_3_8_448, // 3
            invoke_3_4_484, // 4
            invoke_3_8_484, // 5
            // [...]
            invoke_3_8_888, // 15
        };
        return allfuns[fun->offset](fun->orig, a0, a1, a2);
    }
I generate all of the functions by arity and types and then compute an array offset of them ahead of time (so read has an offset of 5 since it returns an 8 byte value and its arguments take a 4 byte, 8 byte, and then 4 byte value).

Without this trick, I'd have to use very non-portable assembler to do the same invocation (OK, I'd use libffi or dyncall's already prepackaged very non-portable assembler, which I may end up with anyway) to make this function call.

Re: Ask HN: Favorite pointer tricks in C?

#22

Post by dspeyer »

Dav3xor wrote: post #16

pointers to structs for things like network protocols... struct packet_header { uint from_addr; uint to_addr; ushort flags; ... } packet *p; read(socket, somebuf, sizeof(packet)); p = &somebuf; printf("from = %u to = %u flags = %u\n",p->from_addr, p->to_addr, p->flags);

Won't this leave all multi-byte values in network endianness?

Re: Ask HN: Favorite pointer tricks in C?

#23

Post by Jach »

I remembered another one, the teleporting turtle algorithm. http://www.penzba.co.uk/Writings/TheTeleportingTurtle.html It's a neat way to determine if there are loops in a linked list (among many other uses).

We start with the turtle and rabbit pointing to the head, and then on each clock tick we advance the rabbit by one step. After a while, assuming we've neither found the end of the list nor caught the turtle, we teleport the turtle to the rabbit's position, double the length of time we're willing to wait, then go again.

Re: Ask HN: Favorite pointer tricks in C?

#24

Post by tptacek »

dspeyer wrote: post #22
Dav3xor wrote: post #16

pointers to structs for things like network protocols... struct packet_header { uint from_addr; uint to_addr; ushort flags; ... } packet *p; read(socket, somebuf, sizeof(packet)); p = &somebuf; printf("from = %u to = %u flags = %u\n",p->from_addr, p->to_addr, p->flags);

Won't this leave all multi-byte values in network endianness?

Yes, but so do the OS socket data structures, which is why htons() and htonl() are in the first chapter of any book on network programming.

The bigger problem with this scheme is alignment, although we appear to have outgrown architectures that will blow up when you get this wrong.

Re: Ask HN: Favorite pointer tricks in C?

#25

Post by tptacek »

* Using pointer offsets to get to the stack frame pointer, and then walking the frame pointer backwards to get the call stack.

* Using && to take the address of a jump label.

* Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.

Re: Ask HN: Favorite pointer tricks in C?

#26

Post by jmkeyes »

Dav3xor wrote: post #16

pointers to structs for things like network protocols... struct packet_header { uint from_addr; uint to_addr; ushort flags; ... } packet *p; read(socket, somebuf, sizeof(packet)); p = &somebuf; printf("from = %u to = %u flags = %u\n",p->from_addr, p->to_addr, p->flags);

Don't use structures as lenses over unchecked input data.

Re: Ask HN: Favorite pointer tricks in C?

#27

Post by cjtenny »

jonsen wrote: post #4

Would you care to share the learning objectives you are fulfilling with pointer tricks in C? Or if it's just some extracurricular entertainment?

I'm teaching the class as a part of ESP's Splash @ MIT, a two-day educational outreach program. Thousands of middle and high school students swarm our campus just for this weekend, and MIT students/community/other teach whatever they want. I'm teaching this as a one-hour class, with two sections (that is, two times), for a bit of entertainment and to make this world a minimally more bug-free place... or something along those lines.

Re: Ask HN: Favorite pointer tricks in C?

#28

Post by scumola »

Compare pointers rather than compare strings: convert all words in a dictionary to a trie structure. Then, each leaf of the tree (a word) is a pointer. A phrase or sentance can be a list of pointers. Pointer compares are mondo-faster when comparing two pointers than walking down two strings.

Re: Ask HN: Favorite pointer tricks in C?

#29

Post by Dav3xor »

tptacek wrote: post #24
dspeyer wrote: post #22

Earlier quoted context omitted.

Won't this leave all multi-byte values in network endianness?

Yes, but so do the OS socket data structures, which is why htons() and htonl() are in the first chapter of any book on network programming. The bigger problem with this scheme is alignment, although we appear to have outgrown architectures that will blow up when you get this wrong.

You do have to be careful, it can be annoying on ARM chips certainly. If you're using GCC, __attribute__ ((packed)) fixes alignment issues.

This method is so much less error prone than pulling stuff out a byte at a time. Plus you can use unions for network addresses, etc.

It's a simplified example to show what you can do.

Re: Ask HN: Favorite pointer tricks in C?

#30

Post by tptacek »

Dav3xor wrote: post #29
tptacek wrote: post #24

Earlier quoted context omitted.

Yes, but so do the OS socket data structures, which is why htons() and htonl() are in the first chapter of any book on network programming. The bigger problem with this scheme is alignment, although we appear to have outgrown architectures that will blow up when you get this wrong.

You do have to be careful, it can be annoying on ARM chips certainly. If you're using GCC, __attribute__ ((packed)) fixes alignment issues. This method is so much less error prone than pulling stuff out a byte at a time. Plus you can use unions for network addresses, etc. It's a simplified example to show what you can do.

It's a good trick, but I disagree that it's the right way to do it. My preferred idiom looks something like:

  s->field1 = ld32(&cp, ep); 
  s->field2 = ld16(&cp, ep); 
  s->field3 = ld16(&cp, ep); 
  s->field4 = ld8(&cp, ep); 
  s->field5 = ld8(&cp, ep); 
  s->field6 = ld32(&cp, ep);
You can just about automate this with a macro (you need to macro out the structure fields and use them both for the structure declaration and the field expansion), but the extra function call there gives you an opportunity to be defensive about e.g. buffer sizes, never blows up alignment, and isn't appreciably slower.
Post reply on HN