Coding style question

[Simon F]

You don't have to go way back to find a CPU without barrel shifter. The Pentium 4 has a 'logarithm shifter'. It's a (conditional) 1-bit shifter followed by a 2-bit shifter, followed by a 4-bit shifter, ... , and finally a 16-bit shifter (for operands up to 32-bit). It works by taking the shift amount and using the first least significant bit (LSB) to determine whether the 1-bit shifter should shift or not, using the second LSB for the 2-bit shifter, etc. This way every combination can be made.

Well, AFAIU, apart from "barrel" meaning it can support rotations, what you've described is what I've always understood a barrel shifter to be. <shrug>

EG: An 8-bit shifter

As for speed/size it only requires O(N*Log2(N)) MUX units (and a short critical path) and so is relatively small - a multiplier, for example, is an O(N^2) device and has a pig of a critical path.

 

[Basic]

Humus:
If you want to go on a space-hunt, a quick start could be to open a cygwin window or Linux shell, and type:

grep -r -n -E '[^ ]' * | grep -r -E '^(Audio|Imaging)'

... but you probably knew that.

I don't like to be restricted to 80 chars per line. But I avoid to make them too much longer. Code past 100 chars would be very rare. Tactical comments could go up to maybe 140 (rarely).

I also use 1920x1440 resolution when programming. But I don't want to fullsize the editor. And even if I had an infinitely wide monitor, i find too long lines rather hard to read.

Simon F:
I don't print source.

Ah, but there were CPUs that didn't have a barrel shifter unit too

There still are rather new CPUs that don't. I do a lot of microcontroller programming. And it's common to not have division, and only single step shifts.

I also do DSP programming, and there I often outperform the compiler with a factor 10 if I switch to assembler. I just can't believe how bad code a supposedly good compiler can produe (yes, with optimization turned to max). Combine that with that the compiler doesn't support all features in the CPU, and you're in for a letdown.

Simon F again:
Yes, that's what I think of as a barrel shifter. I doubt that it would be significantly faster to do it with a N-way mux for each of the N bits. In fact, it's quite possible that it's slower.
And with a few extra gates you can modify that design to be controllable and support left/right, logical/arithmetic, and shift/rotate.

 

[Nick]

Well, AFAIU, apart from "barrel" meaning it can support rotations, what you've described is what I've always understood a barrel shifter to be.

Here you can find diagrams of both a 16-bit log shifter and 16-bit barrel shifter. Without modification neither is capable of rotation, but it's easy to add. Digital Integrated Circuits agrees with this definition.

I must admit though that using 'barrel' for rotation-capable shifters sounds very logical. It's possible that the term became so common that now it's only used to differentiate with the operation of log shifters. Google returns a small number of hits for "logarithmic barrel shifter".

 

[arjan de lumens]

While a right-shift only correctly implements division-by-power-of-2 correctly if the input number is unsigned, it is fairly simple to correct for the case where you are doing a division of a signed-number-by-power-of-2. In the case where your input number is negative, just add the power-of-2 minus 1:

int divby16( int p ) { return p / 16; }
int divby16_again( int p ) { return (p + ((p >> 31) & 15))>>4; }

As for barrel-shifters versus log-shifters: either one should be at least as fast in hardware as a plain old adder/subtracter of the same width.

And as for division in hardware: full integer division is still a mostly unsolved problem - unlike shifts and multiplies, there doesn't exist any known fast hardware algorithms for integer division (floating-point division is actually easier). Most processors just fall back on a repeated-subtract-and-shift method, where the running time is proportonal to the number of bits in the input - the fastest one I have heard about is probably that of AMD K6 (18 cycles for a 32-bit division; the same processor could do an 80-bit FMUL with a latency of 2 cycles! )

 

[Xmas]

int divby16_again( int p ) { return (p + ((p >> 31) & 15))>>4; }

Shouldn't it be * instead of &? And don't you still need to keep the MSB?

int divby16_roundtoneginf( int p ) { return (p >> 4) + (((p >> 31) * 15) << 28); }
int divby16_roundtozero( int p ) { return ((p + ((p >> 31) * 15)) >> 4) + (((p >> 31) * 15) << 28); }

The first one is keeping the MSB while shifting the others, like the x86 instruction SAR does. This rounds towards negative infinity. To round towards zero, you have to add 15 for negative numbers.


EDIT: actually, both could work (my variant only after the edit) depending on the implementation. The result of a right shift of a signed value is undefined. Your code assumes propagation of the MSB, mine doesn't. It would only be portable with a cast to unsigned int.

 

[Simon F]

The result of a right shift of a signed value is undefined.

That doesn't sound correct.

A signed shift is undefined, e.g. x << -N, as is shifting by more than the number of bits, X >> 1893737, but -x >> 3 is legal.

 

[Bob]

That doesn't sound correct.

Indeed. It's not undefined, it's implementation-defined.

implementation-defined behavior
unspecified behavior where each implementation documents how the choice is made
2 EXAMPLE An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.

 

[arjan de lumens]

While it is true that right-shifting a negative signed number can theoretically behave differently on different platforms, does anyone know even one platform/compiler in existence where the signed right-shift does NOT cause replication of the MSB? (to me, it sounds much like platforms with 40-bit doubles, non-2's complement integers, 9-bit chars, etc, all of which are perfectly OK by the C standard but tend to be quite rare to find in practice.)

Also, even if it is a problem, you can circumvent it with a preprocessor check (as the various operands of the language are required to behave the same way in the preprocessor as in the core language itself)

#if ( (-1) >> 1) >= 0
#define SIGNED_RIGHT_SHIFT_BROKEN
#endif

 

[Simon F]

Indeed. It's not undefined, it's implementation-defined.

I just re-read K&R and indeed it does state that (in the final line of the final paragraph!)

What brain-dead CPU doesn't have an Arithmetic Right Shift instruction??

IMHO any machine that doesn't then doesn't deserve to have my code.

 

[DemoCoder]

There still are rather new CPUs that don't. I do a lot of microcontroller programming. And it's common to not have division, and only single step shifts.

The last CPU I programmed that didn't have division and only single step shifts was a 6502.

 

[ShootMyMonkey]

The last CPU I programmed that didn't have division and only single step shifts was a 6502.

Yes... Good ol' C64... Okay, so that was a 6510, but there's only minuscule differences (address 0000 and 0001 and so on). I still have mine, but lately, I only muck with the SID, and that's just for the hell of it.

Still, a microcontroller and a CPU are not typically in the same class.

BTW, if you want to see an example of really bizarre coding style, you might want to look at the source in a certain middleware package which shall remain nameless... Example --

void Foo(  int i32_bar1,  float f32_bar2  )
    {
        bool blah = (  ( (f32_bar2 / i32_bar1) > FLT_EPSILON ) == true  );
        // -- whitespace --

        // -- whitespace --
        if (blah)
            {
                DoStuff(f32_bar2);
                DoOtherStuff(i32_bar1);
                // -- commentBlock --
                #if 0
                    {
                        // DoStuff does stuff while DoOtherStuff does other stuff
                        // I was dropped on my head as a child which is why I code like this.
                    }
                #endif
                // -- commentBlock --
            }
        // -- whitespace --

        // -- whitespace --
    }

I myself went to a university where if you didn't drop down your braces to a newline, many professors would fail you. One I had actually had a gag punishment set up with the mayor where you'd get 2 hours of jail time (wouldn't go on your record, though) if you continued braces on the same line. Either way, I was used to that style in the first place because it's just more generic in my eyes (especially if you put in sub blocks with the braces around them so that you can easily comment out whole blocks).

Of course, I'd worked two jobs in Texas, where everybody preferred the straight-lining style, which I don't completely mind. Though I find the "} else {" portions a bit ick as far as consistency of what lines up with what.

But this style... I don't know what the hell drives someone to adopt something like that. The double indenting is one thing, but nesting his whitespace in comment tags? At best, I can imagine they use some tools that might behave a little more compliantly with such tags...

 

[KimB]

I have seen problems with whitespace in Fortran 77 compilers, so maybe it's a holdover from that....Fortran is still popular, sadly, among scientific applications.

 

[ShootMyMonkey]

That's conceivably possible considering it was physics middleware. But the nesting of comments inside comment tags which contain a #if 0 comment which itself nests a block which holds the actual comments. That's... well... whatever.

I'm also not sure why the growing whitespace in nested parentheses (in case you didn't notice that one, that's also consistent throughout the codebase). For example --

([color=red]...[/color]([color=red]..[/color]([color=red].[/color](stuff) || stuff[color=red].[/color]) && stuff[color=red]..[/color]) ^ stuff[color=red]...[/color])

I might have ended up doing that if I lived in lisp a lot since brackets and parens are 60% of your code. But seriously, it seems rather overkill.

 

[Colourless]

While it is true that right-shifting a negative signed number can theoretically behave differently on different platforms, does anyone know even one platform/compiler in existence where the signed right-shift does NOT cause replication of the MSB? (to me, it sounds much like platforms with 40-bit doubles, non-2's complement integers, 9-bit chars, etc, all of which are perfectly OK by the C standard but tend to be quite rare to find in practice.)

Also, even if it is a problem, you can circumvent it with a preprocessor check (as the various operands of the language are required to behave the same way in the preprocessor as in the core language itself)

#if ( (-1) >> 1) >= 0
#define SIGNED_RIGHT_SHIFT_BROKEN
#endif

Assuming the base architechture doesn't have 'strange' implentation of signed integers (i.e. the architecture is 2's compliment), then the following code would do sign replication if the hardware always shifts in zeros.

x >> shift | (x>=0?0:~((~0)>>shift));

I would of course expect if a compiler were to implement a signed right shift like that for there to be a performance warning... the comparison is not ideal.

 

[Rodéric]

What do you prefer (operator>>)

	is >> fTime;
	is.ignore( 2, '(' ) >> rotation;
	is.ignore( 2, ')' );

or

	char cSkip;
	is >> fTime >> cSkip >> rotation >> cSkip;

BTW, is there any other alternative I might have missed ?

 

[KimB]

Well, the second one is more readable, but I think will only work if there is no whitespace. So the first is often better for ASCII data files.

 

[Rodéric]

Well, the second one is more readable, but I think will only work if there is no whitespace. So the first is often better for ASCII data files.

In fact whitespace and similar characters (such as tabs) are skipped automagically.
I have implemented the second, I prefer it too, was wondering what would be the 'correct' way...

 

[KimB]

Hrm...I knew that was true when you attempt to input a non-character type, but I thought inputting a character type would give the next character, whitespace or no? Guess I haven't tested it myself, though.

 

[Basic]

scanf("%f ( %f )", &fTime, &rotation);

The streams in C++ have their nice points. But in most cases, they are horrible for readability.

[edit] I wonder when I should learn the difference between singular and plural.[/edit]

 

[Simon F]

scanf("%f ( %f )", &fTime, &rotation);

The streams in C++ has it's nice points. But in most cases, it's horrible for readability.

Give that man some positive rep!