Ask HN: Favorite pointer tricks in C?
27 comments
What I think takes the cake is this:
array[index] == index[array]
You didn't really spell out why this trick works:
array[index] == *(array + index) == *(index + array) == index[array]array + index == index + array needs justification
One expects the generic + in a+i to get expanded to raw addition .+. and raw multiplication .x. with s the size of elements of the array
So I'm guessing that the real reason that the trick works is that generic + has three methods with signatures
One expects the generic + in a+i to get expanded to raw addition .+. and raw multiplication .x. with s the size of elements of the array
a .+. s .x. i
So I'm guessing that the real reason that the trick works is that generic + has three methods with signatures
int + int
array + int
int + arrayThe same as above, only using Pointer Arithmetic instead of Array Subscripting:
*(array + index) == *(index + array)
*(&array[0] + index) == *(index + &array[0])Yep. And if teaching that to a bunch of middle or high schoolers, I would add that pointer arith works in increments of sizeof(array[0]) bytes. If you're not careful about operator precedence in moderately complicated expressions, that could come back to bite you.
This is a fantastic way to show younger or beginning programmers to think beyond what the code is supposed to denote and consider how it works in reality--in other words, the hacker's perspective. A naive programmer takes array[index] at face value. The hacker gets the idea that array[index] is just *(array + index) deeply enough to make a perverse joke out of it.
The canonical evil pointer trick is using prev_xor_next to construct a doubly linked list.
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:
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.
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);
rv = abstractInvoke(fun, args[0], args[1], args[2]);
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);
}
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.
This isn't terribly portable FWIW. Not all calling conventions massage data into either a 32-bit or 64-bit argument. In particular, passing structs by value has some interesting rules even in the common calling conventions.
It will certainly work for 90% of the common function types out there and is a pretty common trick.
It will certainly work for 90% of the common function types out there and is a pretty common trick.
Copy-free contiguous subsets of arrays are fairly simple but often convenient. If you want elements 5 through 33 of big_array, you just get a pointer to element 5, and keep track separately of the length. A common case is where you split an array into two non-overlapping subparts, in which case, if you no longer need the original, you can treat each subpart as if it were a separate array. Saves the work of allocating two new arrays for the split parts, which is necessary in many other languages. Useful for efficiently implementing things like decision-tree learners.
Also useful for storing parse results:
"<a href='blah'>"
"<a\0href\0'blah\0>"
This is how strtok returns tokens too.
Incidentally I only found this after trying:
Incidentally I only found this after trying:
char tmp[] = "cat,mat,sat";
char *t;
t = strtok(tmp,",");
while(t != NULL){
printf("%s\n",t);
t = strtok(NULL,",");
}
I like the trick of using the last few bits of aligned pointers to store something useful. It's tricky and has to be done correctly. A class wrapper around the pointer would be better.
For e.g., a constraint in an AVL tree requires that the difference in sizes of left and right subtrees be -1, 0 or 1 (just 3 values, which requires 2 bits). A 4-byte aligned pointer would be enough. =)
For e.g., a constraint in an AVL tree requires that the difference in sizes of left and right subtrees be -1, 0 or 1 (just 3 values, which requires 2 bits). A 4-byte aligned pointer would be enough. =)
This trick has been around for a very long time. I remember Tempus Editor on Atari ST (remember those?) using 8 bits of address registers for additional storage (as only 24 bits out of 32 were used for addressing).
This trick is often seen in language interpreters. Two widely used examples are Emacs Lisp and Mozilla Spidermonkey Javascript.
this is how v8 does tagged pointers.
You can demonstrate pointer arithmetic by showing how you would work with the strstr function. It's the clearest and most understandable reason for someone to see why you'd even discuss this topic I think. I talk to some people without C experience and they hear that idea and get scared. I usually explain how strstr works and that seems to always make sense to them.
Good luck!
Good luck!
char buf[1024]; /* should be enough */
I actually write this a lot in my code. Not code that I intend to share with others, of course. But I do find it amusing about the value I put in brackets. I find it amusing that I have an OCD-like predisposition to make it a power of two. And I find it amusing how the number between the brackets has increased over the last ten years, from a frugal 64 to an opulent 1024. This, to me, is progress.
I actually write this a lot in my code. Not code that I intend to share with others, of course. But I do find it amusing about the value I put in brackets. I find it amusing that I have an OCD-like predisposition to make it a power of two. And I find it amusing how the number between the brackets has increased over the last ten years, from a frugal 64 to an opulent 1024. This, to me, is progress.
In fact, a lot of code does this to avoid mallocs. Just be sure to check the length before you put anything into the buffer.
Also, making it a power of 2 is a good idea if you are concerned about alignment.
Also, making it a power of 2 is a good idea if you are concerned about alignment.
Also, making it a power of 2 is a good idea if you are concerned about alignment.
Actually, there are many reasons why this may not be the case. Remember back to when you implemented a user-space memory allocator. One of the most straightforward algorithms is to use power-of-two blocks with varying coalescing algorithms. The problem that you get with your style and this malloc implementation is that, since you need to store memalloc metadata in the block (probably), each block has just slightly less than a power of two space, which means a block request for a power of two will always waste an enormous amount of space by pushing up to the next power of two block size.
Now, this "power of two allocation is best" misconception is so widespread that many memory allocators actually purposefully account for the case where the memory allocation is a power of two and make their block sizes just slightly larger. Just goes to show you what minor things can do to performance.
Actually, there are many reasons why this may not be the case. Remember back to when you implemented a user-space memory allocator. One of the most straightforward algorithms is to use power-of-two blocks with varying coalescing algorithms. The problem that you get with your style and this malloc implementation is that, since you need to store memalloc metadata in the block (probably), each block has just slightly less than a power of two space, which means a block request for a power of two will always waste an enormous amount of space by pushing up to the next power of two block size.
Now, this "power of two allocation is best" misconception is so widespread that many memory allocators actually purposefully account for the case where the memory allocation is a power of two and make their block sizes just slightly larger. Just goes to show you what minor things can do to performance.
This avoids allocation and is safe (the cost of two extra compares is low because they'll branch the same way all the time, so you'll get branch prediction power)
char *bufp;
uint8_t buf[1024];
if (need_sz >= 1024)
bufp = malloc(need_sz);
else
bufp = buf;
....
if (bufp != buf) free(bufp);It's kind of an anti-pattern, but I've found this to actually enhance clarity in a few places:
int moved = (is_reading ? read : write)(fd, buf, len);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.
One that comes to mind:
Others: virtual function tables, function pointers inside of structs that take a "this" argument effectively giving you OOP, opaque pointers to give compile- and run-time private encapsulation...
struct name {
int namelen;
char namestr[1];
};
struct name *makename(char *newname)
{
struct name *ret =
malloc(sizeof(struct name)-1 + strlen(newname)+1);
/* -1 for initial [1]; +1 for \0 */
if(ret != NULL) {
ret->namelen = strlen(newname);
strcpy(ret->namestr, newname);
}
return ret;
}
Others: virtual function tables, function pointers inside of structs that take a "this" argument effectively giving you OOP, opaque pointers to give compile- and run-time private encapsulation...
The correct way to write this is to not use /1/ in the size of namestr, it's to use a simple []. This tells subsequent programmers that you are using variable length structures. In older compilers, the metaphor was to use '0', but C99 (maybe even earlier) got everyone using [].
Here's a nice discussion in StackOverflow, including a bunch of C++ guys saying to just use Vectors, which ignores the entire point of getting a structure with only one memory allocation:
http://stackoverflow.com/questions/688471/variable-sized-str...
Here's a nice discussion in StackOverflow, including a bunch of C++ guys saying to just use Vectors, which ignores the entire point of getting a structure with only one memory allocation:
http://stackoverflow.com/questions/688471/variable-sized-str...
From GCC: ISO C90 does not support flexible array members.
and:
ISO C forbids zero-size array 'namestr'
Therefore I contest that your way is the "correct" way, especially since most C code is not C99 code. Also I'd probably never use this in C++. If you want to let subsequent programmers know you're using the variable length structure, add the comment: /* unwarranted chumminess with the compiler */
Therefore I contest that your way is the "correct" way, especially since most C code is not C99 code. Also I'd probably never use this in C++. If you want to let subsequent programmers know you're using the variable length structure, add the comment: /* unwarranted chumminess with the compiler */
* 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.
* 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.
* Using && to take the address of a jump label.
Had to look that one up...turns out it's a GCC trick that allows you store the address of a jump label into a pointer to void. Later on, you can do "goto *ptr" to jump back to that address. Neat. See http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
(You obviously already know this...just putting it here in case anyone else hasn't heard of it and is curious)
Had to look that one up...turns out it's a GCC trick that allows you store the address of a jump label into a pointer to void. Later on, you can do "goto *ptr" to jump back to that address. Neat. See http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
(You obviously already know this...just putting it here in case anyone else hasn't heard of it and is curious)
Being a gcc extension to the C language, I recommend this construct never be used and certainly not taught.
> Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.
This is awesome beyond words. If I stumbled across this in the wild I would flip flop between awe and disgust until my head exploded.
Let me guess, "SMTP verb" is not a hypothetical example?
This is awesome beyond words. If I stumbled across this in the wild I would flip flop between awe and disgust until my head exploded.
Let me guess, "SMTP verb" is not a hypothetical example?
There are at least three common mistakes involving tricks like this:
1. Alignment. Many CPUs will trap (or worse) if accessing a 32-bit quantity at a non-aligned address.
2. Endianness. Needless to say, the 32-bit value read for a given string depends on the machine endianness.
3. Aliasing. Casting between different pointer types can result in a violation of the C aliasing rules and, with a little bad luck, incorrect results.
1. Alignment. Many CPUs will trap (or worse) if accessing a 32-bit quantity at a non-aligned address.
2. Endianness. Needless to say, the 32-bit value read for a given string depends on the machine endianness.
3. Aliasing. Casting between different pointer types can result in a violation of the C aliasing rules and, with a little bad luck, incorrect results.
Good to see you on hn.
This is also the basis for the fourcc's used in multimedia. Checking them only requires an integer compare.
Nginx does this too under certain circumstances...check out the ngx_strN_cmp macros in ngx_http_parse.c. (where N is an integer from 3..9)
> Casting a u_int32_t over a 4-byte string (like an SMTP verb) to get a value you can switch() on.
How do you ensure your code is portable between the architectures with different endianness ? One trick may be using htonl on the u_int32_t to get it to a canonical format, but probably there would be better approaches ?
How do you ensure your code is portable between the architectures with different endianness ? One trick may be using htonl on the u_int32_t to get it to a canonical format, but probably there would be better approaches ?
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.
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.
implementing linked lists the way the linux kernel does, that is: each node contains one pointer for each list it can be part of, that pointer's position is determined using some offset_of( field, name) macro.
I've recently started using offsetof in my own code, it's a pretty neat operator. Useful for nested structs, where you have a child but need to reference the parent.
Now I won't spell out actual "pointer tricks" but try to give some context in which these tricks might naturally be used:
I think that data structures like trees are a nice thing to continue once the fundamental properties of pointers have been discussed. (pointer to left, right and data...).
Then sketch out the operations necessary to insert elements, and then explain how pivoting the tree makes it stay performant. This gives you a lot of opportunity to use pointers-to-pointers and so on.
It's a thing that can be nicely visualized on a whiteboard, and it has relevance for students to understand things like databases or filesystems.
If you care to elaborate, you could continue explaining the pitfalls of multithreading, or locking all or parts of the tree during updates, making updates visible in a atomic way... but that gets's out of your "not too simple/crazy" limit pretty fast.
You could also make up a nice producer/consumer example where parts of data that has to be processed is passed around by pointers, stored in linked lists, sliced up/combined. Processing images (rotating tiles), or drawing fractals in parts of memory pointed to by some variable comes to mind.
I think that data structures like trees are a nice thing to continue once the fundamental properties of pointers have been discussed. (pointer to left, right and data...).
Then sketch out the operations necessary to insert elements, and then explain how pivoting the tree makes it stay performant. This gives you a lot of opportunity to use pointers-to-pointers and so on.
It's a thing that can be nicely visualized on a whiteboard, and it has relevance for students to understand things like databases or filesystems.
If you care to elaborate, you could continue explaining the pitfalls of multithreading, or locking all or parts of the tree during updates, making updates visible in a atomic way... but that gets's out of your "not too simple/crazy" limit pretty fast.
You could also make up a nice producer/consumer example where parts of data that has to be processed is passed around by pointers, stored in linked lists, sliced up/combined. Processing images (rotating tiles), or drawing fractals in parts of memory pointed to by some variable comes to mind.
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.
Pointer tricks are dirty and scare the elders. cjtenny is playing the childless uncle who talks about things no parent would. Kids that age will eat it up :-)
Instead of using a while loop to iterate through a linked list, consider using a for loop.
Node * iter;
for (iter=root; iter != NULL; iter=iter->next) {
/* iter->object; */
}
size_t strlen(char * str) {
char * cur;
for(cur=str; *cur; ++cur);
return (cur-str);
}
void reverse(char * str) {
char *i,*j, tmp;
for (i=str, j=(str+strlen(str)-1); i < j; ++i,++j) {
tmp = *i;
*i = *j;
*j = tmp;
}Shouldn't that be --j in your reverse function?
Anyhow, when asked to write those on a blackboard, I typically do this:
Anyhow, when asked to write those on a blackboard, I typically do this:
size_t strlen(char* start) {
char* end=start;
while(*end) ++end;
return (end-start);
}
void reverse(char* i) {
char* j=(i+strlen(i)-1);
for (; i < j; ++i,--j) {
*i ^= *j;
*j ^= *i;
*i ^= *j;
}Yup, --j.
Also, the XOR version probably isn't worth the complexity.
Also, the XOR version probably isn't worth the complexity.
True in practice, but on a blackboard during an interview, it obviates the need to recode for the follow-up "now reverse the string in place" request.
size_t strlen(char *s)
{
size_t i = 0;
while(*s++) i++;
return i;
}void strcpy(char s1, char s2) { while((s1++) = (s2++)); }
A trick to save memory:
If you have a struct/class with a lot of members that are usually set to zero or some other initial value, you can store them in a "lookaside" structure that is hung off a global hash table with the pointer of the original object as the hashtable key. You can then use a bitfield to keep track of which members actually have interesting data.
So -- accessing the member would look something like this:
If you have a struct/class with a lot of members that are usually set to zero or some other initial value, you can store them in a "lookaside" structure that is hung off a global hash table with the pointer of the original object as the hashtable key. You can then use a bitfield to keep track of which members actually have interesting data.
So -- accessing the member would look something like this:
int MyClass::get_foo() {
if (foo_set_)
return global_lookaside[this].foo;
return 0;
}My favorite pointer trick is a simple one. I learned it when I had to implement it (in 64-bit) in a C compiler.
Simply, you can subtract pointers. Let's say you're walking a string from the front and from the back at the same time, and want to find the length of the substring. Well, you don't have to use indeces, just do this:
Simply, you can subtract pointers. Let's say you're walking a string from the front and from the back at the same time, and want to find the length of the substring. Well, you don't have to use indeces, just do this:
int len = back_ptr - front_ptr;
[deleted]
I am not zure whether it fits what you call 'relatively simple', but Knuth's "Dancing links" (http://en.wikipedia.org/wiki/Dancing_Links) would make my list.
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);
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.
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.
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.
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);
If you're willing to use packed structs, here's a neat one when you're dealing with e.g., the entry controls in VMX.
From my virtual machine work:
From my virtual machine work:
struct vmx_entry_ctrls {
union {
uint32_t value;
struct {
uint_t rsvd1 : 2;
uint_t ld_dbg_ctrls : 1;
uint_t rsvd2 : 6;
uint_t guest_ia32e : 1;
uint_t smm_entry : 1;
uint_t no_dual_monitor : 1;
uint_t rsvd3 : 1;
uint_t ld_perf_glbl_ctrl : 1;
uint_t ld_pat : 1;
uint_t ld_efer : 1;
uint_t rsvd4 : 16;
} __attribute__((packed));
} __attribute__((packed));
} __attribute__((packed));You may want to show them how you can generate code by emitting assembly hex-codes into a block of memory and then _call_ the block of code after casting it into a function pointer.
Modern hardware and operating systems require special care when doing this. Firstly, the D-cache must be cleaned and the I-cache invalidated for the relevant memory addresses. This is because the CPU does not in general maintain coherency between these caches for performance reasons (writing instructions is rare). Secondly, memory protection must be set to allow execution of the generated code. Some systems even forbid pages being writeable and executable at the same time in order to make code injection attacks that little bit harder.
By modern hardware I assume you do not mean x86? Self-modifying code (without flushing the I-cache) is still allowed even on the latest processors. Modern OSes indeed do not mark all pages read/execute by default, but that takes a 1-line mprotect() or VirtualProtect() to change. Also, on RISC architectures, D-caches are generally not cleared as part of that process. After all, you are writing instructions, not data.
To the store instruction everything is data, even if it happens to be instructions. Stores initially go the L1 D-cache, and unless the I and D caches are coherent, explicit cleaning (D) and invalidating (I) is required. Maybe they are coherent on x86, but I know with certainty that they are not on for example ARM.
x86 is cache-coherent; we can directly modify code at runtime and expect things to work.
Copy a string in one line:
while (*dst++ = *src++);I wish an HNer had taught me C in high school.
String literals are implicitly pointers and pointers are mostly equivalent to arrays.
char digitAsChar = "0123456789"[digitAsInt%10];
char digitAsChar = "0123456789"[digitAsInt%10];
[deleted]
void strcpy(char *s, char *d) {
while(*d++ = *s++);
}your arguments are backwards and you didn't return dst.
foo[5] is the same thing as * (foo + 5) (since "foo" is the address of the first element), which is equivalent to * (5 + foo) which is equivalent to 5[foo]! EDIT: hn ate up my * s.
I'm teaching a class to a bunch of high school and middle school students tomorrow who've all had moderate experience with programming. I'm covering pointer basics in C as a light intro or refresher, then focusing on cool (but relatively simple / not too crazy) tricks/tips/etc (e.g. stack walking, function pointer arrays). Care to share any of your favorite small pointer tricks with me for the class?
Thanks :)
-Cam