clearing low order bits / making a multiple of power of 2

[Joe Wright]

I hate to be the bearer of bad news, but 0 is not a power of 2.

True indeed. An integral power of two is represented by an unsigned
integer with precisely one bit set to 1. It is trivial to test for:

unsigned is_p2(unsigned u) {
unsigned ret = 0;
if (u) ret = (u & u-1) == 0;
return ret;
}

 

[Tim Rentsch]

With two's complement representation, I think it will always
round towards negative infinity if "size" is any
integer type. [snip]
Not quite. It's possible in this case that the '&' with a
negative operand will yield a trap representation.

I can't find any explicit indication of this, but in any case it is
highly unlikely in practice.

[snip]
The explicit indication is in 6.2.6.2 p2, together with the
description of how '&' works.

Because the bitwise AND of the padding bits in the (promoted) operands may
generate a trap representation?

No that's not what I meant; it isn't necessary that there
be any padding bits. Rather, because the bitwise AND of the
{sign+value} bits in the expression (with size being an int):

size & -4

can result in a representation of sign bit of 1 and all other
bits 0, which is specifically allowed by 6.2.6.2 p2 to be a
trap representation; in particular it's specifically allowed
under two's complement.

 

[Alex Fraser]

No that's not what I meant; it isn't necessary that there
be any padding bits. Rather, because the bitwise AND of the
{sign+value} bits in the expression (with size being an int):

size & -4

can result in a representation of sign bit of 1 and all other
bits 0, which is specifically allowed by 6.2.6.2 p2 to be a
trap representation; in particular it's specifically allowed
under two's complement.

Hmm, I guess it changed between N869 and the actual specification. What you
say makes sense, although I've never come across an implementation where it
is the case.

Alex

 

[Lawrence Kirby]

On Sun, 04 Sep 2005 16:33:07 +0100, John Devereux wrote:

....

Yes, I reported before my results on gcc-arm. (3.3.2).


But, I just tried with the latest gcc (4.1) and it now compiles all
three methods down to the same single machine instruction!

bic r0, r0, #3

So there is no excuse for me not to use the correct method.

For unsigned types this is trivial, but for signed types, in C99
certainly, these should produce different results. For example on 2's
complement systems -23 - (-23%4) is -20, but -23 & -4 is -24. As such the
BIC instruction alone would not be a general correct implementation of
size -= size % 4

Lawrence

 

[Alexei A. Frounze]

....

For unsigned types this is trivial, but for signed types, in C99
certainly, these should produce different results. For example on 2's
complement systems -23 - (-23%4) is -20, but -23 & -4 is -24. As such the
BIC instruction alone would not be a general correct implementation of
size -= size % 4

A negative size is a brain damaged thing.
You can't have negative amount of countable objects. Otherwise that size
isn't really a size but is rather something else, an integer number taking
on both non-negative and negative values in general, like a coordinate.

Alex

 

[John Devereux]

On Sun, 04 Sep 2005 16:33:07 +0100, John Devereux wrote:

...


For unsigned types this is trivial, but for signed types, in C99
certainly, these should produce different results. For example on 2's
complement systems -23 - (-23%4) is -20, but -23 & -4 is -24. As such the
BIC instruction alone would not be a general correct implementation of
size -= size % 4

My compiler does indeed produce different code for signed types (as it
should).

int size;
...
size -= size % 4;

Gets blown up to:
mov r2, r0, asr #31
mov r2, r2, lsr #30
add r3, r0, r2
and r3, r3, #3 ; 0x3
rsb r3, r2, r3

The other two expressions produce the same bic instruction as before.

A negative value would be an error here anyway. I would normally
declare "size" as unsigned. (Is this a good rule in general? Or should
one reserve "unsigned" for bit patterns?) If I forget, and declare it
signed, I guess I will end up with sightly less compact code (but
still correct).

(I hope above is still on topic, I am only showing the assember
listing to illustrate the difference the signed types make to the C
expressions).

 

[Tim Rentsch]

Larry's comment is worth remembering. I didn't mention this
before because I thought it might confuse the discussion, but
part of the reason 'size -= size%4' is preferable is because the
result works (if what you want is to round toward zero). Also,
as Larry pointed out recently under a different subject heading,
using '&' with negative arguments can produce surprising results
on implementations that don't use two's complement. Doing

size &= -4;

when size is an int on a signed magnitude implementation isn't
going to do what you want is size is negative. So that's another
reason to prefer using 'size -= size%4'.

My compiler does indeed produce different code for signed types (as it
should).

int size;
...
size -= size % 4;

Gets blown up to:
mov r2, r0, asr #31
mov r2, r2, lsr #30
add r3, r0, r2
and r3, r3, #3 ; 0x3
rsb r3, r2, r3

The other two expressions produce the same bic instruction as before.

A negative value would be an error here anyway. I would normally
declare "size" as unsigned. (Is this a good rule in general? Or should
one reserve "unsigned" for bit patterns?) If I forget, and declare it
signed, I guess I will end up with sightly less compact code (but
still correct).

Most likely the declaration should be 'size_t size;', which
not-completely-coincidentally makes 'size' be an unsigned type.
Is 'size' supposed to hold the size of an object in char units,
like what sizeof returns?

(I hope above is still on topic, I am only showing the assember
listing to illustrate the difference the signed types make to the C
expressions).

Right.

 

[John Devereux]

Larry's comment is worth remembering. I didn't mention this
before because I thought it might confuse the discussion, but
part of the reason 'size -= size%4' is preferable is because the
result works (if what you want is to round toward zero). Also,
as Larry pointed out recently under a different subject heading,
using '&' with negative arguments can produce surprising results
on implementations that don't use two's complement. Doing

size &= -4;

when size is an int on a signed magnitude implementation isn't
going to do what you want is size is negative. So that's another
reason to prefer using 'size -= size%4'.

A negative size is an error anyway, as far as I am concerned. The only
reason I can see to worry about it is if I accidently declare it as
"int" instead of "unsigned int". I could then assign a large unsigned
int to it such that it "overflows" and becomes negative. For this
scenario the size &= -4 might be better after all!

Basically all I am doing is manipulating pointers for some low level
programming. I wanted to ensure that they are kept word aligned.

So I have code like:

int osTaskCreate(void (*task_addr)(void),
void * p, /* points to storage for tasks stack */
int size) /* size of stack area in bytes */
{
...

size &= -4; /* ensure word aligned */
memset(p,0xee,size); /* clear stack area */

....

Most likely the declaration should be 'size_t size;', which
not-completely-coincidentally makes 'size' be an unsigned type.
Is 'size' supposed to hold the size of an object in char units,
like what sizeof returns?

Yes, of course, I forgot about size_t for some reason! size_t
is guaranteed unsigned, isn't it?

....

 

[Tim Rentsch]

Basically all I am doing is manipulating pointers for some low level
programming. I wanted to ensure that they are kept word aligned.

So I have code like:

int osTaskCreate(void (*task_addr)(void),
void * p, /* points to storage for tasks stack */
int size) /* size of stack area in bytes */
{
...

size &= -4; /* ensure word aligned */
memset(p,0xee,size); /* clear stack area */

I see. Definitely using 'size_t size' would be indicated
here in that case.

Yes, of course, I forgot about size_t for some reason! size_t
is guaranteed unsigned, isn't it?

Yes, size_t is always an unsigned integer type.

 

[Chris Torek]

size &= -4; /* ensure word aligned */
Yes, of course, I forgot about size_t for some reason! size_t
is guaranteed unsigned, isn't it?

The size_t type is an unsigned integral type. It could, at least
technically speaking, be an alias for "unsigned short" or "unsigned
char", though, and those could widen (under the normal promotion
rules) to plain (signed) int, in which case "size &= -4" would
not do the right thing.

Practically speaking, "size &= -4" will work fine. But I actually
prefer to write "size &= ~3", or in this case, "size &= ~(size_t)3",
myself. This may be due to writing too much assembly code over
the years, and reading "&=~" as the "bit-clear operator".

In the oddball case -- where size_t is, e.g., unsigned short and
unsigned short widens to signed int -- my preferred method will
"do the right thing" even on a ones'-complement machine. But the
"&= -4" will work for all size_t variables on "sensible" C systems,
and even on "non-sensible but two's complement" systems. It also
has the arguable advantage of encoding the power of two more
obviously:

size &= -32; /* round down to multiple of 32 */

vs:

size &= ~(size_t)31; /* round down to multiple of 32 */

Then again, in my experience, one tends to want these things to
round up, rather than down, in which case:

size = (size + 31) & ~(size_t)31;

is appropriate (except when size > SIZE_T_MAX - 31).