stealing two bits from a pointer in c [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 9 years ago.

Improve this question

I'm trying to steal two LSB bits from address and I have written the following inline functions. I want to confirm if this works on both 64 and 32 bit machines.

I used stealing bits from a pointer post as reference.

I get a weird bug where getAddress() returns 0x100

0x1 is fine as setFlag1(NULL) will return this address

0x2 is fine as setFlag2(NULL) will return this address

0x11 is also fine as setFlag1(NULL) and setFlag2(NULL) will return this address

But I'm not sure what combination will return 0x100

#define UINTPTR_MAX_XOR_WITH_1 (uintptr_t) (UINTPTR_MAX ^ 0x1)
#define UINTPTR_MAX_XOR_WITH_2 (uintptr_t) (UINTPTR_MAX ^ 0x2)
#define UINTPTR_MAX_XOR_WITH_3 (uintptr_t) (UINTPTR_MAX ^ 0x3)

struct node
{
    unsigned long key;
    struct node* lChild;    //format <address,flag2,flag1>
    struct node* rChild;    //format <address,flag2,flag1>
};

static inline struct node* getAddress(struct node* p)
{
    return (struct node*)((uintptr_t) p & UINTPTR_MAX_XOR_WITH_3);
}

static inline bool isFlag2(struct node* p)
{
    return (uintptr_t) p & 0x2;
}

static inline bool isFlag1(struct node* p)
{
    return (uintptr_t) p & 0x1;
}

static inline struct node* setFlag1(struct node* p)
{
    return((struct node*) (((uintptr_t) p & UINTPTR_MAX_XOR_WITH_1) | 0x1));
}

static inline struct node* unsetFlag1(struct node* p)
{
    return((struct node*) (((uintptr_t) p & UINTPTR_MAX_XOR_WITH_1)));
}

static inline struct node* setFlag2(struct node* p)
{
    return((struct node*) (((uintptr_t) p & UINTPTR_MAX_XOR_WITH_2) | 0x2));
}

Answer 1

The various function depend on UINTPTR_MAX having its 2 LSBits set. Re-coded to eliminate that dependency.

Some simplifications.

Performed comparison for bool return.

Be sure these functions, when called, were properly declared or prototyped. Else the return value is assumed to be int and could explain the 0x100 return.

The problem may still lie elsewhere. Are you expecting calls like setFlag1(p) to set p's bit (which code does not do) or return a pointer with the bit set (which code does)?

static inline struct node* getAddress(struct node* p) {
  return (struct node*)((uintptr_t) p & ~((uintptr_t) 3));
}

static inline bool isFlag1(struct node* p) {
  return ((uintptr_t) p & 1) != 0;
}

static inline bool isFlag2(struct node* p) {
  return ((uintptr_t) p & 2) != 0;
}

static inline struct node* setFlag1(struct node* p) {
  return (struct node*) ((uintptr_t) p | 1);
}

static inline struct node* unsetFlag1(struct node* p) {
  return (struct node*) ((uintptr_t) p & ~((uintptr_t) 1));
}

static inline struct node* setFlag2(struct node* p)
  return (struct node*) ((uintptr_t) p | 2);
}

static inline struct node* unsetFlag2(struct node* p) {
  return (struct node*) ((uintptr_t) p & ~((uintptr_t) 2));
}

[Edit] In review, it is certain that UINTPTR_MAX 2 LSBits must be 1. See @Kaz comment above.

Answer 2

The bug is probably not related to this tagging scheme at all.

It is possible for getAddress to return the address 0x100: you just have to feed it any of the inputs 0x100 through 0x103.

All that your getAddress function does is strip out the two least significant bits in order to recover an aligned pointer. Since 0x100 is clear in its two least significant bits, getAddress is doing its job.

GIGO: garbage in, garbage out!

Add some tracing to print the values that are going into getAddress.

Addresses like 0x100 sometimes result when a null pointer is dereferenced to obtain the address of a structure member: null_pointer->something_at_offset_256. And of course, in general, they can arise in any number of ways.