>"Chris Torek" <no****@elf.eng .bsdi.com> wrote in message

news:bo******* ***@elf.eng.bsd i.com...
[much snippage] len = c1 * 256 + c2; /* if big-endian */

len = c2 * 256 + c1; /* if little-endian */

In article <tA************ *******@twister 01.bloor.is.net .cable.rogers.c om>,

nobody <no****@nowhere .non> wrote:Wouldn't left shift be better? Or are today's compilers "smart" enough

to do this kind of stuff themselves? /*Someone had mentioned this

possibility earlier (particular case was multiplication by 2).*/

Assuming there is no overflow -- and if "len" is at least

unsigned int, and c1 and c2 are in the range [0..255], then

we can make sure that there is none by replacing "256" with

"256U" in each case -- then writing either of:

len = (c1 << 8) + c2;

or len = c1 * 256 + c2;

makes no difference, as a left-shift is equivalent to a multiply.

Of course these should be expressed as:

len = ((unsigned int)c1 << 8) + c2;

and len = c1 * 256U + c2;

respectively.

As for whether one form or the other is "better", it depends on

what you intend to convey to a (human) reader. Any compiler worth

what you paid for it will optimize "c1 * 256U" (or even c1*256,

without the U) into a left shift, and -- in the absence of overflow

-- left shifts are defined in terms of multiplication. (In the

presence of overflow, neither is strictly defined by the C standards,

and a compiler can use the shift anyway on any typical modern CPU.)

Thus, whether you write "what you mean" or "how to do it" is in a

sense irrelevant, as they are isomorphic.

Even the division-by-shifting optimization is easy for compilers

to implement, although here it is more likely to occur for unsigned

operands, because a compiler must typically include some "compensati on"

code for signed divison. This is because:

y = x >> 2;

vs y = x / 4;

is typically not the same when x is negative. For instance, (-1)

/ 4 is usually 0 (and I think is *required* to be 0 in C99), while

(-1) >> 2 is usually -1, on today's machines. Note, however, that

while left shift is *defined* in terms of multiplication -- in both

C89 and C99 -- right shift is not defined in terms of division

except for non-negative "x". Thus, in this case, you really *must*

write "what you mean" instead of "how to do it", as the two are

not necessarily synonymous.

<begin OT>

For the curious, the "compensati on" code for a negative dividend

(and positive divisor) -- remember in x / y, x is the dividend and

y is the divisor -- works out to the following, all assuming 2s

complement and an arithmetic right-shift:

/* divide signed input "x" by divisor, whose log2 is d2 */

int divide_by_power _of_two(int x, int divisor, int d2) {

int adj;

/* required: (1 << d2) == divisor */

adj = (x & SIGNBIT) ? divisor - 1 : 0;

return (ux + adj) >> d2;

}

The idea here is that, e.g., when dividing by 4 (d2 == 2), we want

-1 to give 0, -2 to give 0, -3 to give 0, but -4 to give -1; -5

through -7 should also be -1, while -8 should be -2; and so on.

If x is nonnegative, x >> d2 gives the right answer, but if x is

negative, it gives the wrong answer unless x is an even multiple

of the divisor, otherwise it gives a value one too small (-1 instead

of 0, -2 instead of -1, and so on). Adding (positive) 3 gives the

right answer for -1 through -3 and leaves -4 at -1, which shifts

to -1; and so on. An equivalent trick is to add 1 to the result

if any "1" bits are shifted out during the right-shift operation,

but this is harder to test on typical machines -- the FPU has

hardware to collect such bits (in the "sticky bit" part of IEEE FP

processing), but the integer unit lacks it. The calculation of

the (x&SIGNBIT) adjustment value can, however, be done branchlessly

by shifting x the appropriate number of bits right, e.g., 31 for

32-bit x, to produce an all-ones mask for negative values and

all-zeros for nonnegative, then ANDing this mask with (divisor-1).

On a typical RISC we get something like:

mov x, reg # assuming x is already in a register

asr reg, 31, reg # where asr is arithmetic shift right

and reg, 3, reg # for divisor == 4

add reg, x, reg

asr reg, 2, reg # again for divisor == 4

# final result is now in "reg"

The constants (31, 3, and 2 here) are "number of bits in x that

are not the sign bit", "divisor - 1", and "log2 divisor". For

small divisors these usually fit in the instruction format -- most

RISCs have constant fields that go to at least 255, if not higher;

4095 is not unusual. All of this is only a win if the divide takes

more cycles than the four instructions above. Assuming a single

barrel or funnel shifter and two ALUs, the four instructions take

two cycles, while a typical integer divide is at least four cycles

and as long as 31 or 100 or so cycles, depending on the CPU, so

this is indeed a win, and the compiler should use it.

Of course, if the CPU has a single-cycle divide, or if the dividE

is "parallelizable " and there is other work to do before referring

to the result-value register, it is better just to do "idiv x, 4,

reg". On the (old-only?) MIPS, where you move the values into the

mul/div unit, it is something of a toss-up -- the divide runs in

parallel to any remaining work, but the extra moves consume extra

cycles.

<end OT>

--

In-Real-Life: Chris Torek, Wind River Systems

Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603

email: forget about it

http://67.40.109.61/torek/index.html (for the moment)

Reading email is like searching for food in the garbage, thanks to spammers.