Constant expressions

[jacob navia]

Continuing with my tutorial about C I have added a small text
about constant expressions.

Comments welcome.
--------------------------------------------------------------

Constant expressions
-------------------

The standard defines constant expressions as follows:

A constant expression can be evaluated during translation rather than
runtime, and accordingly may be used in any place that a constant may
be.

Constant expressions can have values of the following type:

o Arithmetic. Any arithmetic operations are allowed. If floating point
is used the precision of the calculations should be at least the same
as in the run time environment.

o A null pointer constant.

o The address of an object with global scope. Optionally an integer
offset can be added to the address.

Since constant expressions are calculated during compilation, even
inefficient algorithms are useful since the execution time is not
affected.

For instance Hallvard B Furuseth proposed (in [1]) a set of clever
macros to calculate the logarithm base 2 of a number during compilation:

/*
* Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<[8, 16, 32, 64].
* Inefficient algorithm, intended for compile-time constants.
*/
#define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))
#define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255)))
#define LOG2_32BIT(v) \
(16*((v)>65535L) + LOG2_16BIT((v)*1L >>16*((v)>65535L)))
#define LOG2_64BIT(v)\
(32*((v)/2L>>31 > 0) \
+ LOG2_32BIT((v)*1L >>16*((v)/2L>>31 > 0) \
Clever isn't it?

So much clever that I have been unable to understand how they work. I
just tested this with the following program:

#include <math.h>
#include <stdio.h>
int main(void)
{
printf("LOG2_32BIT(35986)=%ld\n",LOG2_32BIT(35986));
printf("log2(35986.0)=%g\n",log2(35986.0));
}
OUTPUT:
LOG2_32BIT(35986)=15
log2(35986.0)=15.1351

What is also interesting is that lcc-win receives from the preprocessor
the result of the macro expansion. Here is it, for your amusement
(Of course that is a single huge line that I had to cut in several
places to make it fit the text:

#line 17 "tlog2.c"
int main(void)
{
printf("LOG2_32BIT(35986)=%ld\n",(16*((35986)>65535L) +
(8*(((35986)*1L >>16*((35986)>65535L))>255) +(8 - 90/
(((((35986)*1L >>16*((35986)>65535L)) >>8*(((35986)*
1L >>16*((35986)>65535L))>255))/4+14)|1) - 2/((((35986)*
1L >>16*((35986)>65535L)) >>8*(((35986)*1L >>16*((35986)

65535L))>255))/2+1)))));

The compiler calculates all those operations during compilation, and
outputs the 15, that is stuffed into a register as an argument for the
printf call. Instead of calling an expensive floating point library
function you get the result with no run time penalty.


---
[1] In a message to the comp.lang.c discussion group posted on June 28th
2006, 4:37 pm.
You can find the original message in:

https://groups.google.com/group/comp.lang.c/msg/706324f25e4a60b0?hl=en\&

 

[BartC]

int main(void)
{
printf("LOG2_32BIT(35986)=%ld\n",(16*((35986)>65535L) +
(8*(((35986)*1L >>16*((35986)>65535L))>255) +(8 - 90/
(((((35986)*1L >>16*((35986)>65535L)) >>8*(((35986)*
1L >>16*((35986)>65535L))>255))/4+14)|1) - 2/((((35986)*
1L >>16*((35986)>65535L)) >>8*(((35986)*1L >>16*((35986)


The compiler calculates all those operations during compilation, and
outputs the 15, that is stuffed into a register as an argument for the
printf call. Instead of calling an expensive floating point library
function you get the result with no run time penalty.

My gcc seems to compile log2(35986.0) as a constant anyway, which is what
one might expect. And that's even without optimising.

 

[Thomas Richter]

For instance Hallvard B Furuseth proposed (in [1]) a set of clever
macros to calculate the logarithm base 2 of a number during compilation:

/*
* Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<[8, 16, 32, 64].
* Inefficient algorithm, intended for compile-time constants.
*/
#define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))
#define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255)))
#define LOG2_32BIT(v) \
(16*((v)>65535L) + LOG2_16BIT((v)*1L >>16*((v)>65535L)))
#define LOG2_64BIT(v)\
(32*((v)/2L>>31 > 0) \
+ LOG2_32BIT((v)*1L >>16*((v)/2L>>31 > 0) \
Clever isn't it?

So much clever that I have been unable to understand how they work.

LOG2_8BIT is a rational function approximation of the log - it is not
identical to the log and gives false results for x = 0, or for x > 255,
but only then. That is, it matches the output of log(x) by properly
tweaking the coefficients.

LOG2_16 simply uses the functional equation of the log, namely

log(x * b) = log(b) + log(x)

and in this case, b = 256. The same goes for LOG2_32 and LOG2_64 which
simply extend the game to 64 bit by factoring more and more powers out.

Greetings,
Thomas

 

[jacob navia]

Le 15/10/11 01:47, Thomas Richter a écrit :

LOG2_8BIT is a rational function approximation of the log - it is not
identical to the log and gives false results for x = 0, or for x > 255,
but only then. That is, it matches the output of log(x) by properly
tweaking the coefficients.

LOG2_16 simply uses the functional equation of the log, namely

log(x * b) = log(b) + log(x)

and in this case, b = 256. The same goes for LOG2_32 and LOG2_64 which
simply extend the game to 64 bit by factoring more and more powers out.

Well, you are more clever than me... Thanks and I will add your
explanation to the text (of course citing you and not implying
that I figure it out!)

Thanks again.

 

[jacob navia]

Le 14/10/11 23:50, BartC a écrit :

My gcc seems to compile log2(35986.0) as a constant anyway, which is
what one might expect. And that's even without optimising.

Sure, but you wouldn't want to say to beginners that log2(35986)
is a constant expression ...



P.S. Not all compilers do that. Microsoft compiler doesn't, lcc-win
doesn't. I started implementing it some time ago but didn't finish it.

 

[88888 dihedral]

The integer to log2 problem is one of many hackers' delight in computing.

I'll give an example that can be done in call by name/vale/address/reference for this trick.

Suppose that the input x is in the form of 64 bits in width, i.e. 384db in the signal strength,and the question is how to obtain an integer y= log2(x) in an integer in the range 0 to 63. Of course one should remember that log2(1)=0.

1. First check no negative or zero input in the beginning.
2. Now x is an integer that ranges from 1 to ( 2's power of 64 -1), thus one has to determine y in the range 1,2,...63.

3. A binary search like method is enough!

 

[Keith Thompson]

((0.0 + 0.0) / 2.0) does not fit the definition
of "arithmetic constant expression".

(0.0 + 0.0) is not one of the kinds of operands
that an "arithmetic constant expression" is described as having.

Hmm. A literal reading of C99 6.6p8 does seem to imply that:

An _arithmetic constant expression_ shall have arithmetic
type and shall only have operands that are integer constants,
floating constants, enumeration constants, character constants,
and sizeof expressions. Cast operators in an arithmetic constant
expression shall only convert arithmetic types to arithmetic
types, except as part of an operand to a sizeof operator whose
result is an integer constant.

But I find it hard to believe that that was the intent. It implies that
1.0 / 3.0 is an arithmetic constant expression, but (1.0) / 3.0 isn't.

Is this a flaw in the standard, or am I missing something?

 

[Peter Nilsson]

[...]

((0.0 + 0.0) / 2.0) does not fit the definition
of "arithmetic constant expression".

(0.0 + 0.0) is not one of the kinds of operands that
an "arithmetic constant expression" is described as having.

In what way is (0.0 + 0.0) not a floating constant?

Hmm.  A literal reading of C99 6.6p8 does seem to imply that:

    An _arithmetic constant expression_ shall have arithmetic
    type and shall only have operands that are integer constants,
    floating constants, enumeration constants, character constants,
    and sizeof expressions. Cast operators in an arithmetic
constant expression shall only convert arithmetic types to
arithmetic types, except as part of an operand to a sizeof
operator whose result is an integer constant.

But I find it hard to believe that that was the intent.  It
implies that 1.0 / 3.0 is an arithmetic constant expression,
but (1.0) / 3.0 isn't.

In what way? The parentheses in ( expression ) are syntax, not
operators, in the same way that the comma in an argument-
expression-list is just syntax, not an operator.

A parenthesized expression is a primary expression. Its type
and value are identical to those of the unparenthesized
expression. It is an lvalue, a function designator, or a void
expression if the unparenthesized expression is, respectively,
an lvalue, a function designator, or a void expression.

...am I missing something?

Am I?

It seems a greater argument would be that 42 is not an arithmetic
constant expression since they 'shall only have operands...' and
42 is not used as an operand. Not that I'm arguing that!

 

[Keith Thompson]

[...]

((0.0 + 0.0) / 2.0) does not fit the definition
of "arithmetic constant expression".

(0.0 + 0.0) is not one of the kinds of operands that
an "arithmetic constant expression" is described as having.

In what way is (0.0 + 0.0) not a floating constant?

A floating constant is a single floating-point literal; its grammar is
defined in C99 6.4.4.2. 0.0 is a floating-constant; (0.0 + 0.0) is not.

In what way? The parentheses in ( expression ) are syntax, not
operators, in the same way that the comma in an argument-
expression-list is just syntax, not an operator.

(0.0 + 0.0) is an operand of the "/" operator. It's a parenthesized
expression, not any of the permitted kinds of operand listed in
the standard.

A parenthesized expression is a primary expression. Its type
and value are identical to those of the unparenthesized
expression. It is an lvalue, a function designator, or a void
expression if the unparenthesized expression is, respectively,
an lvalue, a function designator, or a void expression.


Am I?

It doesn't say that a parenthesized expression is a constant
expression if the unparenthesized expression is a constant
expression.

It seems a greater argument would be that 42 is not an arithmetic
constant expression since they 'shall only have operands...' and
42 is not used as an operand. Not that I'm arguing that!

Hmm. Well, a hyper-literal reading might imply that, because 42
has no operands, it *is* a constant expression; all its operands
(of which there are none) qualify. But that reading also makes
"x" a constant expression, where x is declared as a variable.

I think that, rather than placing restrictions on operands, the
definition should place those same restrictions on all primary
expressions that are subexpressions of the expression.

 

[jacob navia]

Le 18/10/11 01:04, pete a écrit :

((0.0 + 0.0) / 2.0) does not fit the definition
of "arithmetic constant expression".

(0.0 + 0.0) is not one of the kinds of operands
that an "arithmetic constant expression" is described as having.

Of course it is. The same as ((8+6)/2). Any kind of expressions are
accepted, the only requirement is that the components of the
expression should be constants

For instance:
#define NB_ELEM(Table) (sizeof(Table)/sizeof(table[0]))

Most compilers simplify those expressions even if they are very
complicated as shown in my example.

 

[Keith Thompson]

The more that I think about it,
the more inclined I am to believe
that I misinterpreted what the standard meant.

I do think you misinterpreted what it *means*. I'm not convinced that
you misinterpreted what it actually *says*.

I'd like to see an interpretation of the literal words of the standard
that make ``((0.0 + 0.0) / 2.0)'' -- or even ``(0)'` -- a constant
expression. (I'm sure beyond reasonable doubt that they're intended to
be; I just don't think the standard correctly expresses that intent.)

 

[Tim Rentsch]

Hmm. A literal reading of C99 6.6p8 does seem to imply that:

An _arithmetic constant expression_ shall have arithmetic
type and shall only have operands that are integer constants,
floating constants, enumeration constants, character constants,
and sizeof expressions. Cast operators in an arithmetic constant
expression shall only convert arithmetic types to arithmetic
types, except as part of an operand to a sizeof operator whose
result is an integer constant.

But I find it hard to believe that that was the intent. It implies that
1.0 / 3.0 is an arithmetic constant expression, but (1.0) / 3.0 isn't.

Is this a flaw in the standard, or am I missing something?

The Standard is guilty of sloppy language. Clearly when it talks
about 'operands' in 6.6p8 the intended meaning is only those
operands that are primitive, ie, not any larger expression. I
think most people understand what is meant with no problem (and
indeed the other meaning never occurs to them). If it were being
voted on in comp.std.c, I would vote to clarify this paragraph
(ie, that a clarifying change is warranted), but I don't think
there is any question about what is meant; in other words, for
purposes of comp.lang.c I think it's a non-issue.