2

I'm building a data structure which sets into 64 bit integers a set bit every 2 or 3 bits.

It would be convenient for me if I could alternately also store a pointer in this structure (when they are terminal nodes in a tree, but that's not relevant).

For the purposes of my representation (which guarantees either the highest or second highest bit are set), if it can be assumed that pointers never have their highest two bits set, i.e. this assertion holds: 

void *sixty_four_bit_pointer = a_valid_address(); 
bool always_zero = 0xC000000000000000 & sixty_four_bit_pointer;

then I can do this trick!

Steven Lu
  • 41,389
  • 58
  • 210
  • 364
  • Nope, I've seen Linux use random starting offsets that use the whole 64-bits. – Mysticial Dec 10 '12 at 04:44
  • Okay I guess I'll have to tack on another field in my struct. – Steven Lu Dec 10 '12 at 04:46
  • I read somewhere that some processors have traps explicitly to prevent use of the upper bits for other purposes. – Mysticial Dec 10 '12 at 04:48
  • 5
    It's pretty common to make the assumption that pointers (at least, to things which need alignment) have their low 2 or 3 bits cleared. That hack goes back at least to early Lisp implementations, which is, for example, http://stackoverflow.com/questions/106597/why-are-fixnums-in-emacs-only-29-bits – rici Dec 10 '12 at 04:49
  • Oh actually... I never thought about the other end of the pointer! That might do the trick. Might a `char *` potentially not be aligned? – Steven Lu Dec 10 '12 at 04:50
  • `char` does not require alignment. You either need a data type that is 8-byte aligned, or you can artificially align your pointers. – Raymond Chen Dec 10 '12 at 04:51
  • You can use the low 2 or 3 bits. [Using the extra 16 bits in 64-bit pointers](http://stackoverflow.com/a/18426582/995714) – phuclv Jan 01 '17 at 10:02

1 Answers1

9

This is not safe in general. It's programs that pull tricks like this that led to the /LARGEADDRESSAWARE flag in Windows. (Aka "this is why we can't have nice things.")

What you can do is use the bottom bits instead of the top bits. Since your structure contains a pointer, it is already 8-byte aligned, which means that the bottom three bits are always 0, so you can use those bits as tag bits.

Raymond Chen
  • 44,448
  • 11
  • 96
  • 135
  • It's that the pointer's type must be one that must be 8-byte aligned for me to then be sure that it has three unset low bits. i.e. you're assuming my pointer is a pointer to that struct. Yes? Like, I can't assume a `char*` has low 3 bits unset, but I can assume a `uint64_t*` does. – Steven Lu Dec 10 '12 at 04:52
  • It wasn't clear what the pointer was a pointer to. I thought it was a pointer to your structure (which in turn contains more pointers to other nodes). If it's just a `char *` then you will need to impose the external alignment yourself. (I.e., make sure your `char *` pointers are 8-byte aligned.) – Raymond Chen Dec 10 '12 at 15:01