Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #25897 > unrolled thread

Limitations and workarounds to expressions defining size of an array

Back to article view | Back to comp.lang.c

Contents

  Limitations and workarounds to expressions defining size of an array Francois Grieu <fgrieu@gmail.com> - 2012-09-04 19:14 +0200
    Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-04 14:08 -0400
      Re: Limitations and workarounds to expressions defining size of an array Francois Grieu <fgrieu@gmail.com> - 2012-09-05 09:56 +0200
        Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-05 07:33 -0400
          Re: Limitations and workarounds to expressions defining size of an array Francois Grieu <fgrieu@gmail.com> - 2012-09-05 23:39 +0200
            Re: Limitations and workarounds to expressions defining size of an array Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-05 18:11 -0400
      Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-05 07:17 -0400
    Re: Limitations and workarounds to expressions defining size of an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-09-04 19:18 +0100
    Re: Limitations and workarounds to expressions defining size of an array Kaz Kylheku <kaz@kylheku.com> - 2012-09-04 18:41 +0000
      Re: Limitations and workarounds to expressions defining size of an array "BartC" <bc@freeuk.com> - 2012-09-04 20:22 +0100
        Re: Limitations and workarounds to expressions defining size of an array Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-04 17:07 -0400
          Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-04 17:25 -0400
            Re: Limitations and workarounds to expressions defining size of an array Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-04 18:24 -0400
              Re: Limitations and workarounds to expressions defining size of an array Keith Thompson <kst-u@mib.org> - 2012-09-04 17:29 -0700
          Re: Limitations and workarounds to expressions defining size of an array army1987 <army1987@ask-for-it.invalid> - 2012-09-04 21:26 +0000
            Re: Limitations and workarounds to expressions defining size of an array army1987 <army1987@ask-for-it.invalid> - 2012-09-04 21:31 +0000
              Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-04 17:41 -0400
                Re: Limitations and workarounds to expressions defining size of an array army1987 <army1987@ask-for-it.invalid> - 2012-09-05 20:45 +0000
                  Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-05 17:23 -0400
                    Re: Limitations and workarounds to expressions defining size of an array army1987 <army1987@ask-for-it.invalid> - 2012-09-05 21:30 +0000
                      Re: Limitations and workarounds to expressions defining size of an array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-09-05 23:04 +0100
                      Re: Limitations and workarounds to expressions defining size of an array Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-05 18:17 -0400
                      Re: Limitations and workarounds to expressions defining size of an array James Kuyper <jameskuyper@verizon.net> - 2012-09-05 18:29 -0400
              Re: Limitations and workarounds to expressions defining size of an array Kaz Kylheku <kaz@kylheku.com> - 2012-09-04 21:44 +0000
        Re: Limitations and workarounds to expressions defining size of an array Kaz Kylheku <kaz@kylheku.com> - 2012-09-04 21:39 +0000
          Re: Limitations and workarounds to expressions defining size of an array "BartC" <bc@freeuk.com> - 2012-09-04 22:58 +0100
            Re: Limitations and workarounds to expressions defining size of an array Kaz Kylheku <kaz@kylheku.com> - 2012-09-04 22:12 +0000
            Re: Limitations and workarounds to expressions defining size of an array Lowell Gilbert <lgusenet@be-well.ilk.org> - 2012-09-04 18:55 -0400
        Re: Limitations and workarounds to expressions defining size of an array Keith Thompson <kst-u@mib.org> - 2012-09-04 16:51 -0700
          Re: Limitations and workarounds to expressions defining size of an array Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-09-04 20:58 -0400
            Re: Limitations and workarounds to expressions defining size of an array Francois Grieu <fgrieu@gmail.com> - 2012-09-05 10:04 +0200
            Re: Limitations and workarounds to expressions defining size of an array Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 04:47 -0700
              Re: Limitations and workarounds to expressions defining size of an array Keith Thompson <kst-u@mib.org> - 2012-09-07 14:04 -0700
                Re: Limitations and workarounds to expressions defining size of an array Casey Carter <casey_at_carter_dot_net@nospam.invalid> - 2012-09-07 16:40 -0500
                Re: Limitations and workarounds to expressions defining size of an array Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 19:54 -0700
                  Re: Limitations and workarounds to expressions defining size of an array Keith Thompson <kst-u@mib.org> - 2012-09-08 14:15 -0700
                    Re: Limitations and workarounds to expressions defining size of an array lawrence.jones@siemens.com - 2012-09-17 12:09 -0400
          Re: Limitations and workarounds to expressions defining size of an array Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 04:53 -0700
            Re: Limitations and workarounds to expressions defining size of an array "BartC" <bc@freeuk.com> - 2012-09-07 13:07 +0100
              Re: Limitations and workarounds to expressions defining size of an array Keith Thompson <kst-u@mib.org> - 2012-09-07 14:08 -0700
              Re: Limitations and workarounds to expressions defining size of an array Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 19:41 -0700
    Re: Limitations and workarounds to expressions defining size of an array "BartC" <bc@freeuk.com> - 2012-09-04 20:26 +0100
    Re: Limitations and workarounds to expressions defining size of an array Barry Schwarz <schwarzb@dqel.com> - 2012-09-04 14:14 -0700
    Re: Limitations and workarounds to expressions defining size of an array Tim Rentsch <txr@alumni.caltech.edu> - 2012-09-07 04:41 -0700
    Re: Limitations and workarounds to expressions defining size of an array army1987 <army1987@ask-for-it.invalid> - 2012-09-07 13:32 +0000

Page 1 of 3  [1] 2 3  Next page →

#25897 — Limitations and workarounds to expressions defining size of an array

I'm trying to figure out the exact limitations that (possibly:
various versions of ISO/IEC 9899) C puts to expressions defining
the size of a plain array at compile time, and how to workaround
that.

An application would be, given EXPECTED, to define at compile
time an array with EXPECTED + 12*sqrt(EXPECTED) elements, or
some even more complex formula, as required by
http://stats.stackexchange.com/q/35658/8469


A tentative (not tested)

#define EXPECTED 15000

/* define an array of EXPECTED + 12*sqrt(EXPECTED)
   pointers to struct foo (or slightly more) */
struct foo * bar[
#if (EXPECTED)<900
  #error "unsupported EXPECTED value"
  -1
#elif (EXPECTED)<3600
  (EXPECTED)+360+((EXPECTED)-896)/5
#elif (EXPECTED)<14400
  (EXPECTED)+720+((EXPECTED)-3591)/10
#else
  (EXPECTED)+1440ul+((EXPECTED)-14381ul)/20
#endif
  ];

I think the above works for any EXPECTED>=900 up to
some large value like ULONG_MAX-ULONG_MAX/19 and then some,
and errs on the safe side, with at worse 5% wasted memory;
but this is
- unclear at best;
- painful to extend to lower bounds or less wasted memory;
- hard to generalize to more complex formula involving
  for example log or exp.

Can I
- use floating point at all ?
- if yes: use sqrt, log, exp ?
- or at least, use intermediate values (other than
  macro identifiers) to clarify things and remain below
  the "4095 characters in a logical source line" limit?

I can think of enum as intermediates, and have done that
when computing a CRC at compile time, but they have rather
silly range limitations.


  François Grieu

[toc] | [next] | [standalone]

#25900

On 09/04/2012 01:14 PM, Francois Grieu wrote:
> I'm trying to figure out the exact limitations that (possibly:
> various versions of ISO/IEC 9899) C puts to expressions defining
> the size of a plain array at compile time, and how to workaround
> that.


In C99:
6.7.5.2p1: "... the expression shall have an integer type. If the
expression is a constant expression, it shall have a value greater than
zero."
6.7.5.2p2: "... If an identifier is declared to be an object with static
storage duration, it shall not have a variable length array type."
6.7.5.2p4: "... If the size is an integer constant expression and the
element type has a known constant size, the array type is not a variable
length array type; otherwise, the array type is a variable length array
type."
6.7.5.2p5: "If the size is an expression that is not an integer constant
expression expression: if it occurs in a declaration at function
prototype scope, it is treated as if it were replaced by *; otherwise,
each time it is evaluated it shall have a value greater than zero."

C2011:
Change 6.7.5 => 6.7.6
Add "thread storage duration" as another context where VLAs are prohibited.
Implementation support for VLAs is now optional.

C90:
I don't have a copy of C90 to confirm the exact details of the wording,
but VLAs were added in C99, and were therefore not an option in C90.

> An application would be, given EXPECTED, to define at compile
> time an array with EXPECTED + 12*sqrt(EXPECTED) elements, or
> some even more complex formula, as required by
> http://stats.stackexchange.com/q/35658/8469
> 
> 
> A tentative (not tested)
> 
> #define EXPECTED 15000
> 
> /* define an array of EXPECTED + 12*sqrt(EXPECTED)
>    pointers to struct foo (or slightly more) */
> struct foo * bar[
> #if (EXPECTED)<900
>   #error "unsupported EXPECTED value"
>   -1
> #elif (EXPECTED)<3600
>   (EXPECTED)+360+((EXPECTED)-896)/5
> #elif (EXPECTED)<14400
>   (EXPECTED)+720+((EXPECTED)-3591)/10
> #else
>   (EXPECTED)+1440ul+((EXPECTED)-14381ul)/20
> #endif
>   ];
> 
> I think the above works for any EXPECTED>=900 up to
> some large value like ULONG_MAX-ULONG_MAX/19 and then some,

Correct. All of your expressions have integer type and a constant value,
and except for the first one, have a positive value. Unless I missed
something, they should be acceptable in all versions of the standard.

> and errs on the safe side, with at worse 5% wasted memory;
> but this is
> - unclear at best;
> - painful to extend to lower bounds or less wasted memory;
> - hard to generalize to more complex formula involving
>   for example log or exp.
> 
> Can I
> - use floating point at all ?
> - if yes: use sqrt, log, exp ?

In C90, "No" to both questions. For arrays with static or thread storage
duration, no. However, in C99, for arrays with automatic storage
duration, this is permitted, so long as the entire expression containing
those sub-expressions has an integer type and a positive value. In
C2011, it depends upon whether or not __STDC_NO_VLA__ is pre-#defined by
the implementation.

> - or at least, use intermediate values (other than
>   macro identifiers) to clarify things and remain below
>   the "4095 characters in a logical source line" limit?

Whether or not that's permitted depends upon precisely what you mean by
that phrase - it's not clear from context.

[toc] | [prev] | [next] | [standalone]

#25948

On 04/09/2012 20:08, James Kuyper wrote:
> On 09/04/2012 01:14 PM, Francois Grieu wrote:
>> I'm trying to figure out the exact limitations that (possibly:
>> various versions of ISO/IEC 9899) C puts to expressions defining
>> the size of a plain array at compile time, and how to workaround
>> that.
>
>
> In C99:
> 6.7.5.2p1: "... the expression shall have an integer type. If the
> expression is a constant expression, it shall have a value greater than
> zero."
> 6.7.5.2p2: "... If an identifier is declared to be an object with static
> storage duration, it shall not have a variable length array type."
> 6.7.5.2p4: "... If the size is an integer constant expression and the
> element type has a known constant size, the array type is not a variable
> length array type; otherwise, the array type is a variable length array
> type."
> 6.7.5.2p5: "If the size is an expression that is not an integer constant
> expression expression: if it occurs in a declaration at function
> prototype scope, it is treated as if it were replaced by *; otherwise,
> each time it is evaluated it shall have a value greater than zero."

Yes; also relevant is 6.6p6
  An integer constant expression (.. used to specify .. the size of an
  array ..) shall have integer type and shall only have operands
  that are integer constants, enumeration constants, character
  constants, sizeof expressions whose results are integer constants,
  and floating constants that are the immediate operands of casts.
  Cast operators in an integer constant expression shall only
  convert arithmetic types to integer types, except as part of an
  operand to the sizeof operator.

I read that as C99 NOT allowing (except in automatic context, as a
VLA) even basic use of floating point as in

struct foo * bar[(unsigned)(1000*2.718)];


>>   I hoped at least to use intermediate values (other than
>>   macro identifiers) to clarify things and remain below
>>   the "4095 characters in a logical source line" limit

> Whether or not that's permitted depends upon precisely what you mean
> by that phrase - it's not clear from context.

I was hoping for
// select temporary type
#include <limits.h>
#ifdef ULLONG_MAX
typedef unsigned long long uw;
#else
typedef unsigned long      uw;
#endif
#define UTMP static const uw

#define EXPECTED 15000
UTMP kExpected = EXPECTED;
UTMP kRoot2 = 12*12*kExpected;
// we want ceil(sqrt(12*12*kExpected)), use Newton/Rapson
UTMP kExTmp0 = (uw)3<<(kRoot2>>30 > 0 ? 15 :
                       kRoot2>>24 > 0 ? 12 :
                       kRoot2>>18 > 0 ?  9 :
                       kRoot2>>12 > 0 ?  6 : 3);
UTMP kExTmp1 = (kExTmp0+kRoot2/kExTmp0)/2;
UTMP kExTmp2 = (kExTmp1+kRoot2/kExTmp1)/2;
UTMP kExTmp3 = (kExTmp2+kRoot2/kExTmp2)/2;
UTMP kExTmp4 = (kExTmp3+kRoot2/kExTmp3)/2;
UTMP kExTmp5 = (kExTmp4+kRoot2/kExTmp4)/2;
UTMP kExTmp6 = (kExTmp5+kRoot2/kExTmp5)/2;
UTMP kExTmp7 = (kExTmp6+kRoot2/kExTmp6)/2;
UTMP kExTmp8 = (kExTmp7+kRoot2/kExTmp7)/2;
UTMP kExTmp9 = (kExTmp8+kRoot2/kExTmp8)/2;
UTMP kExTmpA = (kExTmp9+kRoot2/kExTmp9)/2;
UTMP kExTmpB = (kExTmpA+kRoot2/kExTmpA)/2;
UTMP kExTmpC = (kExTmpB+kRoot2/kExTmpB)/2;
UTMP kRoot = kExTmpC+(kExTmpB>kExTmpC?1:0);

struct foo * bar[kExpected+kRoot];


This is not valid C99 (the definition of kRoot2 is invalid);
is that valid in C11? <ot>Note: it seem valid in C++</ot>.

  Francois Grieu

[toc] | [prev] | [next] | [standalone]

#25953

On 09/05/2012 03:56 AM, Francois Grieu wrote:
...
> I was hoping for
> // select temporary type
> #include <limits.h>
> #ifdef ULLONG_MAX
> typedef unsigned long long uw;
> #else
> typedef unsigned long      uw;
> #endif
> #define UTMP static const uw
> 
> #define EXPECTED 15000
> UTMP kExpected = EXPECTED;
> UTMP kRoot2 = 12*12*kExpected;
> // we want ceil(sqrt(12*12*kExpected)), use Newton/Rapson
> UTMP kExTmp0 = (uw)3<<(kRoot2>>30 > 0 ? 15 :
>                        kRoot2>>24 > 0 ? 12 :
>                        kRoot2>>18 > 0 ?  9 :
>                        kRoot2>>12 > 0 ?  6 : 3);
> UTMP kExTmp1 = (kExTmp0+kRoot2/kExTmp0)/2;
> UTMP kExTmp2 = (kExTmp1+kRoot2/kExTmp1)/2;
> UTMP kExTmp3 = (kExTmp2+kRoot2/kExTmp2)/2;
> UTMP kExTmp4 = (kExTmp3+kRoot2/kExTmp3)/2;
> UTMP kExTmp5 = (kExTmp4+kRoot2/kExTmp4)/2;
> UTMP kExTmp6 = (kExTmp5+kRoot2/kExTmp5)/2;
> UTMP kExTmp7 = (kExTmp6+kRoot2/kExTmp6)/2;
> UTMP kExTmp8 = (kExTmp7+kRoot2/kExTmp7)/2;
> UTMP kExTmp9 = (kExTmp8+kRoot2/kExTmp8)/2;
> UTMP kExTmpA = (kExTmp9+kRoot2/kExTmp9)/2;
> UTMP kExTmpB = (kExTmpA+kRoot2/kExTmpA)/2;
> UTMP kExTmpC = (kExTmpB+kRoot2/kExTmpB)/2;
> UTMP kRoot = kExTmpC+(kExTmpB>kExTmpC?1:0);
> 
> struct foo * bar[kExpected+kRoot];
> 
> 
> This is not valid C99 (the definition of kRoot2 is invalid);
> is that valid in C11? <ot>Note: it seem valid in C++</ot>.

Ah - I see the point you're raising now. Sorry for missing it in your
previous message - I didn't notice your use of 'static' in the
#definition of UTMP. Initializers for an object of static storage
duration must be constant expressions. In C++, a const variable
initialized with a constant expression can itself be used as a constant
expression, but in C it is not allowed. You'd have to re-write this as a
single constant expression, and you'll have to be careful to avoid
running into line length limitations if you do so. I haven't checked to
be sure, but you might have settle for fewer iterations.

If you remove the 'static' and define these inside a function, there
should be no problem except with the definition of bar itself, which
requires VLA support. Of course, if you can use a VLA, you wouldn't need
to use such a round-about method to do this, you could simply calculate
the sqrt() directly.
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#25969

On 05/09/2012 13:33, James Kuyper wrote:
> (..) Initializers for an object of static storage
> duration must be constant expressions. In C++, a const variable
> initialized with a constant expression can itself be used as a constant
> expression, but in C it is not allowed. You'd have to re-write this as a
> single constant expression, and you'll have to be careful to avoid
> running into line length limitations if you do so. I haven't checked to
> be sure, but you might have settle for fewer iterations.

I think that I found a conforming workaround: use enums instead
of constants. There is the limitation that enums can only be
trusted to hold 15 bits, but I can workaround that too using
the following ZS and ZG macros.


// select temporary type uw
#include <limits.h>
#ifdef ULLONG_MAX
typedef unsigned long long uw;
#else
typedef unsigned long      uw;
#endif

// Utility macro to set symbol s to value v (60-bit capacity)
#define ZS(s,v) enum{e0##s=(v)&32767,e1##s=(v)>>15&32767,\
e2##s=(v)>>15>>15&32767,e3##s=(v)>>15>>15>>15&32767}

// Utility macro to get value of symbol s (60-bit capacity)
#define ZG(s) (((((uw)e3##s<<15|e2##s)<<15|e1##s))<<15|e0##s)

// Set of macros to compute floor(sqrt(x)) for x>0.
// Find a raw approximation of sqrt(x)
#define SQRT0(x) ((uw)8<<(3*((x)<512?0:(x)>>15<1?1:(x)>>15<64?2:\
(x)>>15>>9<8?3:(x)>>15>>15<8?4:(x)>>15>>15>>9<1?5:\
(x)>>15>>15>>15<1?6:(x)>>15>>15>>15<64?7:(x)>>15>>15>>15>>9<8?8:9)))
// One Newton-Raphson refinement step
#define SQRT1(x,a) (((x)/(a)+(a))/2)
// Four Newton-Raphson refinement steps
#define SQRT4(x,a) (SQRT1(x,SQRT1(x,SQRT1(x,SQRT1(x,a)))))
// Final tweak to get exact value
#define SQRTF(x,a) (SQRT1(x,a)-(SQRT1(x,a)>(a)?1:0))

#define EXPECTED 400000000

// Now we want:
//  struct foo * bar[EXPECTED+ceil(12*sqrt(EXPECTED)];
// that is
//  struct foo * bar[EXPECTED+1+floor(sqrt(12*12*EXPECTED-1)];
#define KVALUE (12*12*(uw)(EXPECTED)-1)
ZS(kExTmp0, SQRT0(KVALUE));             // first approximation
ZS(kExTmp1, SQRT4(KVALUE,ZG(kExTmp0))); // improve..
ZS(kExTmp2, SQRT4(KVALUE,ZG(kExTmp1))); // improve..
ZS(kExTmp3, SQRT4(KVALUE,ZG(kExTmp2))); // improve..
#define KROOT SQRTF(KVALUE,ZG(kExTmp3)) // finalize
struct foo * bar[EXPECTED+1+KROOT];


This works and (as far as I can tell) is conformant, but many
will understandably frown on it as hairy. Especially if we push
it further and implement floating-point-as-enum.


Questions: In C11, what liberties do we have?
In particular,
- can we define the size of a static array (non-VLA)
   using a  static const long  ?
- can we use a  static const long  freely in an
   expression that defines another static const long ?
- can we use floating point arithmetic in expressions defining
   a static const long ?
- can we use exp() and log() in such expressions ?

   Francois Grieu

[toc] | [prev] | [next] | [standalone]

#25972

On 9/5/2012 5:39 PM, Francois Grieu wrote:
> [...]
> Questions: In C11, what liberties do we have?
> In particular,
> - can we define the size of a static array (non-VLA)
>    using a  static const long  ?

     Sure:

	static const long scl = 42;
	static int array[sizeof scl];

     But for the question I think you're really asking, the
answer is No.  First read 6.7.6.2p4 to learn that an array
with a dimension that is not an integer constant expression
is a VLA.  Then read 6.6p6 to find out how an ICE is formed;
note that `static const long' does not match any of the allowed
operands.  Hence an expression using the value of an SCL is
not an ICE, and an array declared with such an expression as
its dimension is a VLA.

> - can we use a  static const long  freely in an
>    expression that defines another static const long ?

     No. 6.6p7-9.

> - can we use floating point arithmetic in expressions defining
>    a static const long ?

     Yes. 6.6p8.

> - can we use exp() and log() in such expressions ?

     No. 6.6p6-9.

     6.6p10 offers a loophole: "An implementation may accept
other forms of constant expressions," so for any particular
compiler some of the Noes may turn to Yesses.  But you wrote
"freely," which I'm interpreting as "works on all C11 compilers,"
and with that understanding the Noes have it.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid
"The speed at which the system fails is usually not important."

[toc] | [prev] | [next] | [standalone]

#25952

On 09/05/2012 03:09 AM, Francois Grieu wrote:
> On 04/09/2012 20:08, James Kuyper wrote:
>> On 09/04/2012 01:14 PM, Francois Grieu wrote:
...
> Yes; also relevant is 6.6p6
>    An integer constant expression (.. used to specify .. the size of an
>    array ..) shall have integer type and shall only have operands
>    that are integer constants, enumeration constants, character
>    constants, sizeof expressions whose results are integer constants,
>    and floating constants that are the immediate operands of casts.
>    Cast operators in an integer constant expression shall only
>    convert arithmetic types to integer types, except as part of an
>    operand to the sizeof operator.
> 
> I read that as C99 NOT allowing (except in automatic context, as a
> VLA) even basic use of floating point as in
> 
> struct foo * bar[(unsigned)(1000*2.718)];

That is correct. Which is why, if you want to do this, it will have to
be an array with automatic storage duration. Does it need to have static
storage duration?

...
> I was hoping for (not tested)
> 
> // select temporary type
> #include <limits.h>
> #ifdef ULLONG_MAX
> #define UTMP static const unsigned long long
> #else
> #define UTMP static const unsigned long
> #endif

I'd recommend using a typedef rather than #define for that purpose. If
you do use a typedef, you should also change the name, since
fully-capitalized names are, by convention, used mainly for macros.

> #define EXPECTED 15000
> UTMP kExpected = EXPECTED;
> UTMP kRoot2 = 12*12*Expected;
> // we want ceil(sqrt(12*12*Expected)), use Newton/Rapson
> UTMP kExTmp0 = (uwl)3<<(kRoot2>>30 > 0 ? 15 :
>                          kRoot2>>24 > 0 ? 12 :
>                          kRoot2>>18 > 0 ?  9 :
>                          kRoot2>>12 > 0 ?  6 : 3);
> UTMP kExTmp1 = (kExTmp0+kRoot2/kExTmp0)/2;
> UTMP kExTmp2 = (kExTmp1+kRoot2/kExTmp1)/2;
> UTMP kExTmp3 = (kExTmp2+kRoot2/kExTmp2)/2;
> UTMP kExTmp4 = (kExTmp3+kRoot2/kExTmp3)/2;
> UTMP kExTmp5 = (kExTmp4+kRoot2/kExTmp4)/2;
> UTMP kExTmp6 = (kExTmp5+kRoot2/kExTmp5)/2;
> UTMP kExTmp7 = (kExTmp6+kRoot2/kExTmp6)/2;
> UTMP kExTmp8 = (kExTmp7+kRoot2/kExTmp7)/2;
> UTMP kExTmp9 = (kExTmp8+kRoot2/kExTmp8)/2;
> UTMP kExTmpA = (kExTmp9+kRoot2/kExTmp9)/2;
> UTMP kExTmpB = (kExTmpA+kRoot2/kExTmpA)/2;
> UTMP kExTmpC = (kExTmpB+kRoot2/kExTmpB)/2;
> UTMP kRoot = kExTmpC+(kExTmpB>kExTmpC?1:0);
> 
> struct foo * bar[kExpected+kRoot];
> 
> Is that valid in C11?

I don't see any problems. Did you have any particular reason for
doubting that it was valid? If so, you might be right - I'm far less
reliable when I say "I see no problems" than when I say "I see a problem".
-- 
James Kuyper

[toc] | [prev] | [next] | [standalone]

#25902

Francois Grieu <fgrieu@gmail.com> writes:

> I'm trying to figure out the exact limitations that (possibly:
> various versions of ISO/IEC 9899) C puts to expressions defining
> the size of a plain array at compile time, and how to workaround
> that.
>
> An application would be, given EXPECTED, to define at compile
> time an array with EXPECTED + 12*sqrt(EXPECTED) elements, or
> some even more complex formula, as required by
> http://stats.stackexchange.com/q/35658/8469
>
>
> A tentative (not tested)
>
> #define EXPECTED 15000
>
> /* define an array of EXPECTED + 12*sqrt(EXPECTED)
>    pointers to struct foo (or slightly more) */
> struct foo * bar[
> #if (EXPECTED)<900
>   #error "unsupported EXPECTED value"
>   -1
> #elif (EXPECTED)<3600
>   (EXPECTED)+360+((EXPECTED)-896)/5
> #elif (EXPECTED)<14400
>   (EXPECTED)+720+((EXPECTED)-3591)/10
> #else
>   (EXPECTED)+1440ul+((EXPECTED)-14381ul)/20
> #endif
>   ];
>
> I think the above works for any EXPECTED>=900 up to
> some large value like ULONG_MAX-ULONG_MAX/19 and then some,
> and errs on the safe side, with at worse 5% wasted memory;
> but this is
> - unclear at best;
> - painful to extend to lower bounds or less wasted memory;
> - hard to generalize to more complex formula involving
>   for example log or exp.
>
> Can I
> - use floating point at all ?

I don't think so, not in an integer constant expression.

> - if yes: use sqrt, log, exp ?

You can't use functions calls, even in floating point constant
expressions!

> - or at least, use intermediate values (other than
>   macro identifiers) to clarify things and remain below
>   the "4095 characters in a logical source line" limit?

I don't know about that.

> I can think of enum as intermediates, and have done that
> when computing a CRC at compile time, but they have rather
> silly range limitations.

If it helps, I thought you might try this:

#define S0 (EXPECTED < 10000 ? 100 : (EXPECTED < 1000000) ? 1000 : 10000)
#define NR(s) (((s) + EXPECTED/(s))/2)
#define SQRT (NR(NR(NR(NR(S0)))))

It is, obviously, Newton-Raphson iteration (4 steps) and gets very close
estimates.  For example, with EXPECTED=2147483647, SQRT=S3=46424 instead
of 46340.  Add another branch to the conditional (to get a better start
estimate) or add another iteration and you get an exact answer.

You can replace the conditional expression with a set of #if's, or even
define S1, S2 etc to keep the expression size down though it's only
about 1500 characters as it is.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#25903

On 2012-09-04, Francois Grieu <fgrieu@gmail.com> wrote:
> Can I
> - use floating point at all ?
> - if yes: use sqrt, log, exp ?

No. Constant expressions cannot contain funtion calls.

I would calculate the size at run-time (possibly caching it for re-use)
and then use malloc to grab the storage.

If I really needed a compile constant which requires a complex computation,
I would do that computation in a build configuration script (written in
some interpreted language which has floating-point support), and have it
spit out an include file.

[toc] | [prev] | [next] | [standalone]

#25905

"Kaz Kylheku" <kaz@kylheku.com> wrote in message 
news:20120904113418.486@kylheku.com...
> On 2012-09-04, Francois Grieu <fgrieu@gmail.com> wrote:
>> Can I
>> - use floating point at all ?
>> - if yes: use sqrt, log, exp ?
>
> No. Constant expressions cannot contain funtion calls.

Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the first 
two compilers I tried.

It's not much of a stretch to allow that to be used as an array dimension, 
the main stumbling block being that 3.0 is not integral, while adding an 
(int) cast makes it look like a runtime expression.

-- 
Bartc 

[toc] | [prev] | [next] | [standalone]

#25912

On 9/4/2012 3:22 PM, BartC wrote:
> "Kaz Kylheku" <kaz@kylheku.com> wrote in message
> news:20120904113418.486@kylheku.com...
>> On 2012-09-04, Francois Grieu <fgrieu@gmail.com> wrote:
>>> Can I
>>> - use floating point at all ?
>>> - if yes: use sqrt, log, exp ?
>>
>> No. Constant expressions cannot contain funtion calls.
>
> Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the
> first two compilers I tried.

     Don't confuse definition with optimization.  Also, try your
compilers on

	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")

... and let us know if they replace it with `3'.

> It's not much of a stretch to allow that to be used as an array
> dimension, the main stumbling block being that 3.0 is not integral,
> while adding an (int) cast makes it look like a runtime expression.

     The presence of an (int) cast does not disqualify an expression
from being an "integer constant expression."  The function call,
however, does.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid
"The speed at which the system fails is usually not important."

[toc] | [prev] | [next] | [standalone]

#25917

On 09/04/2012 05:07 PM, Eric Sosman wrote:
> On 9/4/2012 3:22 PM, BartC wrote:
>> "Kaz Kylheku" <kaz@kylheku.com> wrote in message
>> news:20120904113418.486@kylheku.com...
>>> On 2012-09-04, Francois Grieu <fgrieu@gmail.com> wrote:
>>>> Can I
>>>> - use floating point at all ?
>>>> - if yes: use sqrt, log, exp ?
>>>
>>> No. Constant expressions cannot contain funtion calls.
>>
>> Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the
>> first two compilers I tried.
> 
>      Don't confuse definition with optimization.  Also, try your
> compilers on
> 
> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
> 
> ... and let us know if they replace it with `3'.

That expression has a value of 0. Were you thinking of strspn()? My
compiler has no problems with the following:

#include <math.h>
#include <stdio.h>
#include <string.h>

struct foo{
    int i;
};
int main(int argc, char *argv[])
{
    struct foo *bar[(int)ceil(argc + 12.0*sqrt(argc))];
    printf("bar: %zu\n", sizeof bar/ sizeof *bar);

    int baz[strspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")];
    printf("baz: %zu\n", sizeof baz/ sizeof *baz);
    return 0;
}

Which produces the output:

bar: 13
baz: 3

when invoked with no arguments, and

bar: 32
baz: 3

when invoked with four arguments. Does your compiler have any problems
with it?

[toc] | [prev] | [next] | [standalone]

#25928

On 9/4/2012 5:25 PM, James Kuyper wrote:
> On 09/04/2012 05:07 PM, Eric Sosman wrote:
>> On 9/4/2012 3:22 PM, BartC wrote:
>>> "Kaz Kylheku" <kaz@kylheku.com> wrote in message
>>> news:20120904113418.486@kylheku.com...
>>>> On 2012-09-04, Francois Grieu <fgrieu@gmail.com> wrote:
>>>>> Can I
>>>>> - use floating point at all ?
>>>>> - if yes: use sqrt, log, exp ?
>>>>
>>>> No. Constant expressions cannot contain funtion calls.
>>>
>>> Yet, an expression such as sqrt(9.0) seems to be reduced to 3.0 on the
>>> first two compilers I tried.
>>
>>       Don't confuse definition with optimization.  Also, try your
>> compilers on
>>
>> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
>>
>> ... and let us know if they replace it with `3'.
>
> That expression has a value of 0. Were you thinking of strspn()?

     Indeed, I was.  Too much 'c', I guess.  ;-)

> [...] Does your compiler have any problems
> with it?

     BartC reports the compilers he tested implemented `sqrt(9.0)'
as `3.0', implying that the actual function call was not performed
at run-time.  (He presumably used extra-linguistic means to find
this out.)  He went on to suggest that this somehow put `sqrt(9.0)'
on an equal footing with a "constant expression."  My example was
intended to show another function whose value is knowable before
run-time, hence similar to `sqrt(9.0)', but most likely not similarly
optimized.  That is, I was trying to show the fallacy of reasoning
from observed behavior backward to the Standard, instead of from the
Standard forward to required behavior.

     What I showed instead was carelessness, sigh.

-- 
Eric Sosman
esosman@ieee-dot-org.invalid
"The speed at which the system fails is usually not important."

[toc] | [prev] | [next] | [standalone]

#25935

Eric Sosman <esosman@ieee-dot-org.invalid> writes:
[...]
>             That is, I was trying to show the fallacy of reasoning
> from observed behavior backward to the Standard, instead of from the
> Standard forward to required behavior.
>
>      What I showed instead was carelessness, sigh.

What you showed *in addition* was carelessness.

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
    Will write code for food.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

[toc] | [prev] | [next] | [standalone]

#25918

On Tue, 04 Sep 2012 17:07:39 -0400, Eric Sosman wrote:

>      Don't confuse definition with optimization.  Also, try your
> compilers on
> 
> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
> 
> ... and let us know if they replace it with `3'.

You meant strspn?



-- 
[  T  H  I  S     S  P  A  C  E     I  S     F  O  R     R  E  N  T  ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
  -- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>

[toc] | [prev] | [next] | [standalone]

#25919

On Tue, 04 Sep 2012 21:26:29 +0000, army1987 wrote:

> On Tue, 04 Sep 2012 17:07:39 -0400, Eric Sosman wrote:
> 
>>      Don't confuse definition with optimization.  Also, try your
>> compilers on
>> 
>> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
>> 
>> ... and let us know if they replace it with `3'.
> 
> You meant strspn?

BTW, I'm shocked by the result. It optimizes away the call to strspn but 
it actually calls printf with arguments "%d\n" and 3? WTF?



-- 
[  T  H  I  S     S  P  A  C  E     I  S     F  O  R     R  E  N  T  ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
  -- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>

[toc] | [prev] | [next] | [standalone]

#25922

On 09/04/2012 05:31 PM, army1987 wrote:
> On Tue, 04 Sep 2012 21:26:29 +0000, army1987 wrote:
> 
>> On Tue, 04 Sep 2012 17:07:39 -0400, Eric Sosman wrote:
>>
>>>      Don't confuse definition with optimization.  Also, try your
>>> compilers on
>>>
>>> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
>>>
>>> ... and let us know if they replace it with `3'.
>>
>> You meant strspn?
> 
> BTW, I'm shocked by the result. It optimizes away the call to strspn but 
> it actually calls printf with arguments "%d\n" and 3? WTF?

The only printf() calls explicitly mentioned in this thread so far were
in my example program, which used "%zu", not "%d", so you're presumably
referring to some other program. What does the source code look like?

[toc] | [prev] | [next] | [standalone]

#25963

On Tue, 04 Sep 2012 17:41:25 -0400, James Kuyper wrote:

> On 09/04/2012 05:31 PM, army1987 wrote:
>> On Tue, 04 Sep 2012 21:26:29 +0000, army1987 wrote:
>> 
>>> On Tue, 04 Sep 2012 17:07:39 -0400, Eric Sosman wrote:
>>>
>>>>      Don't confuse definition with optimization.  Also, try your
>>>> compilers on
>>>>
>>>> 	strcspn("BartC", "abcdefghijklmnopqrsBCuvwxyz")
>>>>
>>>> ... and let us know if they replace it with `3'.
>>>
>>> You meant strspn?
>> 
>> BTW, I'm shocked by the result. It optimizes away the call to strspn
>> but it actually calls printf with arguments "%d\n" and 3? WTF?
> 
> The only printf() calls explicitly mentioned in this thread so far were
> in my example program, which used "%zu", not "%d", so you're presumably
> referring to some other program. What does the source code look like?

#include <stdio.h>
int main(void)
{
    printf("%d\n", (int)strspn("BartC", "abcdefghijklmnopqrsBCuvwxyz"));
    return 0;
}



-- 
[  T  H  I  S     S  P  A  C  E     I  S     F  O  R     R  E  N  T  ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
  -- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>

[toc] | [prev] | [next] | [standalone]

#25967

On 09/05/2012 04:45 PM, army1987 wrote:
> On Tue, 04 Sep 2012 17:41:25 -0400, James Kuyper wrote:
> 
>> On 09/04/2012 05:31 PM, army1987 wrote:
...
>>> BTW, I'm shocked by the result. It optimizes away the call to strspn
>>> but it actually calls printf with arguments "%d\n" and 3? WTF?
>>
>> The only printf() calls explicitly mentioned in this thread so far were
>> in my example program, which used "%zu", not "%d", so you're presumably
>> referring to some other program. What does the source code look like?
> 
> #include <stdio.h>
> int main(void)
> {
>     printf("%d\n", (int)strspn("BartC", "abcdefghijklmnopqrsBCuvwxyz"));
>     return 0;
> }

OK, that's roughly what I expected, but I wanted to be sure. In
particular, your "WTF?" left me wondering whether you thought the
optimization was invalid. I'm mildly impressed by that optimization, but
not nearly as much as you were, apparently.

[toc] | [prev] | [next] | [standalone]

#25968

On Wed, 05 Sep 2012 17:23:04 -0400, James Kuyper wrote:

>  In
> particular, your "WTF?" left me wondering whether you thought the
> optimization was invalid.

I don't. But 1) I was surprised that strspn() was optimized away, and 2) 
I seemed to remember seeing a compiler optimizing away printf() some time 
ago, so I expected that if a compiler would do the former it would do the 
latter too.



-- 
[  T  H  I  S     S  P  A  C  E     I  S     F  O  R     R  E  N  T  ]
Troppo poca cultura ci rende ignoranti, troppa ci rende folli.
  -- fathermckenzie di it.cultura.linguistica.italiano
<http://xkcd.com/397/>

[toc] | [prev] | [next] | [standalone]

Page 1 of 3  [1] 2 3  Next page →

Back to top | Article view | comp.lang.c

csiph-web