Left shift by more than 32 bits-->undefined in DEC C?

[Galen Tackett]

We're in the middle of migrating a C application built for Alpha to run on our VMS I64 systems. One of our developers recently came across some bit shifting code that didn't work the same on Alpha and I64.

We've already fixed the broken code. In the process, though, we learned that in HP C the result is undefined if the shift amount is more than the number of bits in an int (= 32). (See section C.5.3 of the HP C Language Reference Manual at http://h71000.www7.hp.com/commercial/c/docs/6180profile_017.html#index_x_593)

Both Alpha and I64 are 64 bit processors. I don't know about I64 but Alpha can do a 64 bit shift in one instruction. So why the 32 bit limit on shifts? Does some standard specify this limitation?

Further, the result is different on I64 than on Alpha.

See the attached file for sample code and output.

If the shift amount is a constant >= 32 the compiler will catch it and give you the %CC-W-SHIFTCOUNT message. Obviously it can't do that when the shift amount is a variable.

Comments are welcome.

[Richard Whalen]

My Itanium Architecture Software Developer's Manual (Revision 2.2), volume 3 says:

Page 3:222 (index says 3:224)

shl - Shift Left

shl r1 = r2,r3
shl r1 = r2,count

The value in r2 is shifted to the left with the vacated bit positions filled with zeroes, and placed in r1. The shift count is interpreted as an unsigned number. If the value is greater and 63, then the result is all zeroes.

Though Alpha and Itanium are 64 bit machines, the VMS heritage comes from a 32 bit machine (VAX). I believe that an int is still considered to be 32 bits and you have to declare the type of your variable as int64 to get a 64 bit value.

[Hoff]

The C language lawyers in the C compiler group were pretty good, and if the operation is listed as undefined, they're quite free to return anything they want.

From what I find, you got caught out by an "undefined". Any shift past 31 is "undefined" for a 32-bit int value.

The sign extension mentioned in your comments is likely unrelated, and appears part of the C argument (integral) promotion; it's in the C standard when converting.

The C code that was posted is not the C code tested.

The following result looks wrong (save via application of the "undefined" clause and the associated "anything goes" mentioned above):
1u << 64 = 00000001

This screams "undefined", as I'd expect a zero here if this actually performed a 64 bit shift on a 32-bit quantity.

And it's also this case that's "different" in the source code posted...

The first few entries are listed as 1u in the printf, I'd expect unsigned. That's a display bug.

[Galen Tackett]

> I believe that an int is still considered to be 32 bits and you have to declare
> the type of your variable as int64 to get a 64 bit value.

You're right about an int still being 32 bits on Alpha and I64.

But check my reference above to the C LRM for a specific statement that defines shift as having a limit of the size of an int (32 bits, of course.)

That's what surprised me--the shift operator is defined to work only up to 32 bits even though both Alpha and I64 cpus can trivially do a 64 bit shift.


But the value "1Lu" on the left of the << in the last four lines of my example is a 64 bit unsigned integer constant with a value of 1.

It works the same if you use a 64 bit unsigned integer variable. I just didn't show that in my code, for brevity.

Plus the pseudo-"sign extension" performed on the result of "1Lu << 31" seems pretty strange.

[Steven Schweda]

In the interest of beating a dead horse past
the point of diminishing returns, it appears
that on Alpha, the shift count is masked down
to six bits. A longer test shows this (in
tedious detail):

alp $ type shift.c
#include
main()
{
int i;
for (i = 0; i <= 128; i++)
{
printf( " %3d %%x%03x %%x%08x\n", i, i, (1<< i));
}
}

alp $ cc shift
alp $ link shift
alp $ run shift
0 %x000 %x00000001
1 %x001 %x00000002
2 %x002 %x00000004
3 %x003 %x00000008
4 %x004 %x00000010
5 %x005 %x00000020
6 %x006 %x00000040
7 %x007 %x00000080
8 %x008 %x00000100
9 %x009 %x00000200
10 %x00a %x00000400
11 %x00b %x00000800
12 %x00c %x00001000
13 %x00d %x00002000
14 %x00e %x00004000
15 %x00f %x00008000
16 %x010 %x00010000
17 %x011 %x00020000
18 %x012 %x00040000
19 %x013 %x00080000
20 %x014 %x00100000
21 %x015 %x00200000
22 %x016 %x00400000
23 %x017 %x00800000
24 %x018 %x01000000
25 %x019 %x02000000
26 %x01a %x04000000
27 %x01b %x08000000
28 %x01c %x10000000
29 %x01d %x20000000
30 %x01e %x40000000
31 %x01f %x80000000
32 %x020 %x00000000
33 %x021 %x00000000
34 %x022 %x00000000
35 %x023 %x00000000
36 %x024 %x00000000
37 %x025 %x00000000
38 %x026 %x00000000
39 %x027 %x00000000
40 %x028 %x00000000
41 %x029 %x00000000
42 %x02a %x00000000
43 %x02b %x00000000
44 %x02c %x00000000
45 %x02d %x00000000
46 %x02e %x00000000
47 %x02f %x00000000
48 %x030 %x00000000
49 %x031 %x00000000
50 %x032 %x00000000
51 %x033 %x00000000
52 %x034 %x00000000
53 %x035 %x00000000
54 %x036 %x00000000
55 %x037 %x00000000
56 %x038 %x00000000
57 %x039 %x00000000
58 %x03a %x00000000
59 %x03b %x00000000
60 %x03c %x00000000
61 %x03d %x00000000
62 %x03e %x00000000
63 %x03f %x00000000
64 %x040 %x00000001 (Mom! He's doing it again!)
65 %x041 %x00000002
66 %x042 %x00000004
67 %x043 %x00000008
68 %x044 %x00000010
69 %x045 %x00000020
70 %x046 %x00000040
71 %x047 %x00000080
72 %x048 %x00000100
73 %x049 %x00000200
74 %x04a %x00000400
75 %x04b %x00000800
76 %x04c %x00001000
77 %x04d %x00002000
78 %x04e %x00004000
79 %x04f %x00008000
80 %x050 %x00010000
81 %x051 %x00020000
82 %x052 %x00040000
83 %x053 %x00080000
84 %x054 %x00100000
85 %x055 %x00200000
86 %x056 %x00400000
87 %x057 %x00800000
88 %x058 %x01000000
89 %x059 %x02000000
90 %x05a %x04000000
91 %x05b %x08000000
92 %x05c %x10000000
93 %x05d %x20000000
94 %x05e %x40000000
95 %x05f %x80000000
96 %x060 %x00000000
97 %x061 %x00000000
98 %x062 %x00000000
99 %x063 %x00000000
100 %x064 %x00000000
101 %x065 %x00000000
102 %x066 %x00000000
103 %x067 %x00000000
104 %x068 %x00000000
105 %x069 %x00000000
106 %x06a %x00000000
107 %x06b %x00000000
108 %x06c %x00000000
109 %x06d %x00000000
110 %x06e %x00000000
111 %x06f %x00000000
112 %x070 %x00000000
113 %x071 %x00000000
114 %x072 %x00000000
115 %x073 %x00000000
116 %x074 %x00000000
117 %x075 %x00000000
118 %x076 %x00000000
119 %x077 %x00000000
120 %x078 %x00000000
121 %x079 %x00000000
122 %x07a %x00000000
123 %x07b %x00000000
124 %x07c %x00000000
125 %x07d %x00000000
126 %x07e %x00000000
127 %x07f %x00000000
128 %x080 %x00000001 (MOM!!!!!)
alp $

So, shifting a 32-bit value by up to 63 bits
works right, and that probably covers the
vast majority of the lame code out there, but
apparently not absolutely all of it.


I _loved_ the rich-text-format attachment,
by the way.


> But the value "1Lu" on the left of the <<
> in the last four lines of my example is a
> 64 bit unsigned integer constant with a
> value of 1.

Sure it is.

alp $ type SIZX.C
#include
main()
{
printf( " sizeof 1Lu = %d.\n", (sizeof 1Lu));
printf( " sizeof 1LLu = %d.\n", (sizeof 1LLu));
}
alp $ cc SIZX
alp $ link SIZX
alp $ run SIZX
sizeof 1Lu = 4.
sizeof 1LLu = 8.
alp $


We're having fun now.

[Galen Tackett]

Hoff,

> The C code that was posted is not the C code tested.

Thanks for catching my scribal errors. That was an attempt to transcribe from a classified system to an unclassified one, with the keyboard/monitor about 6 feet away.

I've attached a corrected copy of the sample program. Hope I haven't botched it again in the process of fixing it. :-)

> The C language lawyers in the C compiler group were pretty good, and if the operation is listed as undefined, they're quite free to return anything they want.

True, of course.

>From what I find, you got caught out by an "undefined". Any shift past 31 is "undefined" for a 32-bit int value.

Yes. The original developer years back blindly relied on the undefined result of this code as it ran on the Alpha. The current maintainer/developer discovered that it ran differently on the I64 and came to me for help.

I turned up the cited statement in the C LRM and pointed it out to him and our other developers. It was easy to fix the code once the problem was located and understood.

>The sign extension mentioned in your comments is likely unrelated, and appears part of the C argument (integral) promotion; it's in the C standard when converting.

Is this really part of one or more C standards? I don't claim to know the innards of the C standards, but I wonder, because--

How can you promote 1U (unsigned 64 bit) to another integral type? It's the largest one there is.

And why would you "sign extend" from bit 31 of a 64 bit unsigned value?

It looks more like the compiler was _de_moting the 64 bit unsigned value to a 32 bit signed value, then sign extending that. I don't know why it would do this.

[Steven Schweda]

And, by the way, sign extension is a
right-shift phenomenon, and is not involved
in any way in a left shift. The confusing
stuff here is completely distinct from any
sign extension.

[Galen Tackett]

All,

I am SO sorry about posting the RTF attachment, and multiple times at that.

I had somehow saved it in both plain text and RTF formats, and clicked the wrong one. If you're still interested, a plain text version is attached.

I'd not knowingly post anything but plain text here.

I blame it Gates, whose !&@#%@\]? OS is the one I used to create the file. And we know it's behind all the world's evils. I'll bet it was a WinSnake that tempted Eve in the first place!

Galen

[Steven Schweda]

> I'd not knowingly post anything but plain
> text here.

Oh, sure. You'd say anything now.

Any mystery remaining, or is all wonderfully
clear at last?

[Galen Tackett]

Once again I have overwhelmed my actual question with sheer verbosity.

The only real questions I have are:

Do the C standards with which HP C V7.1 complies make any kind of statement that would limit the maximum supported shift to either "the number of bits in an int" or explicitly to 32 bits?

If not, it seems to me a needless limitation to have no defined 64 bit shift on a 64 bit platform.

[Steven Schweda · Accepted solution]

> Do the C standards with which HP C V7.1
> complies make any kind of statement that
> would limit the maximum supported shift to
> either "the number of bits in an int" or
> explicitly to 32 bits?

Apparently, you can trust it up to 63 on
Alpha, for either a 32-bit or a 64-bit value.
On IA64, the implementation seems to allow
shift counts larger than 63.

While the HP C document says:

The result of the shift operation is
undefined if the right operand is negative
or if its value is greater than the number
of bits in an int.

I assume that for "in an int" it really meant
"in the left operand", and I'll admit that
when you really _do_ have a 64-bit value,
I'd've expected a left shift by 64 to do
something (rather than nothing).

However:

http://c0x.coding-guidelines.com/6.5.7.html

says:

1175 If the value of the right operand is
negative or is greater than or equal to
the width of the promoted left operand,
the behavior is undefined.

And with that "greater than or equal to",
they pull the rug out from under a complaint
about a 64-bit shift on a 64-bit item.

And RTF or not, your sample code is shifting
32-bit values, not 64-bit values. If you
want to see what happens to actual 64-bit
values, you could use this:

alp $ type shift64.c
#include
main()
{
int i;
for (i = 0; i <= 128; i++)
{
printf( " %3d %%x%03x %%x%016llx\n", i, i, (1LL<< i));
}
}


As before, shift counts on Alpha seem to be
masked at six bits, while on IA64 shift
counts bigger than 63 work as one might hope
(but apparently shouldn't expect).

[Hoff]

There's a different variation of this one around, as Itanium (or it used to) happily process the whole of the shift value (rather than the low six bits Alpha looks at), and it takes a while to shift a huge number of bits.

If this hasn't been tagged in the compiler (and it might have been), you could request a shift by a billion or so. And wait for it.

I'd prefer that anything past the scale of the value being shifted would cough up a zero and continue, or cough up an error, but that doesn't always happen.

This made one of my hints-and-kinks presentations a while back.

[John Reagan]

From the C99 standard, section 6.5.7, Bitwise shift operators:

Semantics

The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

[Steven Schweda]

You're welcome, I'm sure.

[Galen Tackett]

Sorry for having abruptly closed the thread earlier with no explanation...

I do appreciate everyone's comments and have awarded points to each of you.

Thanks for your help.

Galen

[Steven Schweda]

It was educational. If anyone had asked me
what you'd get from a left-shift by 64 on an
Alpha, I wouldn't have hesitated before
saying "zero". I hate educational.

[Steven Schweda]

By the way, is the six-bit shift count an
Alpha hardware thing, or could the C
compiler/RTL be adjusted to let, say, seven
bits slip through? Getting zero from
"1LL << 64" would be much more satisfying
than the current result. (Think of it as an
IA64-compatibility feature?)

[Hoff]

IIRC, the six-bit field is an Alpha instruction implementation; take a look at the LSL and ASL stuff.

[Dennis Handly]

For PA-RISC, the shift register is 5 or 6 bits respectively. Earlier for K&R, there was extra code to test the shift value. Later we realized that ANSI C said it was unspecified, so this extra test was ripped out.

As mentioned by Hoff, IPF will not mask the shift value and shift off to 0. This is also allowed by the Standard.

>If the shift amount is a constant >= 32 the compiler will catch it

That's correct. Some compilers after they warn, set the value to 0, even if the hardware won't.

>Steven: sign extension is a right-shift phenomenon, and is not involved in any way in a left shift.

That's not quite true. The HP3000 had a ASL, Arithmetic Left Shift instruction that would preserve the sign bit on overflow.

[Steven Schweda]

> The HP3000 had a ASL, [...]

Yeah, and the IBM 1130 had a RTE (rotate
right accumulator and extension), but it was
just as hard to get to from C. Maybe harder,
as I don't recall seeing a C compiler for the
1130. (COBOL, FORTRAN, RPG, APL, and BASIC,
but not C.)

Now, if you're looking for a machine with
minimal high-level language support, I
recommend the Univac 422. Assembler and
ELTRAN. (It's amazing what you can get into
512 15-bit words.)

[Hoff]

>>>For PA-RISC, the shift register is 5 or 6 bits respectively. Earlier for K&R, there was extra code to test the shift value. Later we realized that ANSI C said it was unspecified, so this extra test was ripped out.<<<

That's exactly the right decision for a compiler author, as it generates faster executable code for the end user. This when the code is correctly written.

When the code is not correctly written -- and we all know there's a whole lot of this code around -- then removing the check is exactly the wrong decision. There are massive quantities of open source around that are, well, buggy -- this code is often built with a compiler that generates fast code. Compilers that (only) generate fast code even allow this buggy code to survive and prosper.

I've personally found the compromise in the classic DIGITAL compilers invaluable here, as they have traditionally flagged questionable constructs. This made these compilers far more valuable to me. (These diagnostics are typically tied to compiler-level portability diagnostics, to compiler-level range checks, or to optimization settings; they're selectable.)

If I could get the C code past these diagnostic-happy compilers, then I knew I had a much better shot of getting the code to work with compilers that simply generated fast code. And with having working and reliable code at run-time. As a long-time C developer, these better diagnostics were the value-add over gcc and other options. Certainly run-time performance is important, but for me it was (also) the quality of the resulting code, and the lowered costs of supporting the generated code.

Stephen Hoffman
HoffmanLabs LLC

[Richard Whalen]

This thread just became useful to me - I have some code that works on AXP but not IA64 because it does a shift to the left of more than 32 bits!