Constant expressions

Discussion in 'C Programming' started by jacob navia, Oct 14, 2011.

1. jacob naviaGuest

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

--------------------------------------------------------------

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

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) \
>>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:

jacob navia, Oct 14, 2011

2. BartCGuest

"jacob navia" <> wrote in message
news:j7a99l\$23e\$...

> 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.

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

--
Bartc

BartC, Oct 14, 2011

3. Thomas RichterGuest

On 14.10.2011 23:24, jacob navia wrote:

> 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) \
> >>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

Thomas Richter, Oct 15, 2011
4. jacob naviaGuest

Le 15/10/11 01:47, Thomas Richter a écrit :
>>
>> 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.
>

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, Oct 15, 2011
5. jacob naviaGuest

Le 14/10/11 23:50, BartC a écrit :
> "jacob navia" <> wrote in message
> news:j7a99l\$23e\$...
>
>> 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.

>
> 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.

jacob navia, Oct 15, 2011
6. 88888 dihedralGuest

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!

88888 dihedral, Oct 15, 2011
7. Keith ThompsonGuest

pete <> writes:
[...]
> ((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?

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Oct 18, 2011
8. Peter NilssonGuest

Keith Thompson <> wrote:
> pete <> writes:
>
> [...]
>
> > ((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!

--
Peter

Peter Nilsson, Oct 18, 2011
9. Keith ThompsonGuest

Peter Nilsson <> writes:
> Keith Thompson <> wrote:
>> pete <> writes:
>>
>> [...]
>>
>> > ((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.

>> 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.

(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 missing something?

>
> 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.

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Oct 18, 2011
10. jacob naviaGuest

Le 18/10/11 01:04, pete a écrit :
> jacob navia wrote:
>
>> 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.

>
> ((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.

jacob navia, Oct 18, 2011
11. Keith ThompsonGuest

pete <> writes:
> jacob navia wrote:
>>
>> Le 18/10/11 01:04, pete a Ã©crit :
>> > jacob navia wrote:
>> >
>> >> 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.
>> >
>> > ((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

>
> 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.)

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson, Oct 18, 2011
12. Tim RentschGuest

Keith Thompson <> writes:

> pete <> writes:
> [...]
>> ((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?

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.

Tim Rentsch, Jan 25, 2012