9bit arithmetics in C

[Arturi]

Hi all,

what's the trick to perform 9 bit arithmetics in C? I am modeling a
hardware design and I need to perform signed 9bit arith with
saturation.

Any ideas??

Cheers

 

[Ben Pfaff]

what's the trick to perform 9 bit arithmetics in C? I am modeling a
hardware design and I need to perform signed 9bit arith with
saturation.

I don't think that there is a trick. I think that you should
just write some functions to perform the operations that you
need. Have you tried?

 

[Hallvard B Furuseth]

what's the trick to perform 9 bit arithmetics in C? I am modeling
a hardware design and I need to perform signed 9bit arith with
saturation.

If you are lucky, struct s_ninebit { signed int val:9; }". I.e. if your
program does not need to be portable, and your C implementation uses
saturation for bit fields. Don't depend on that unless the compiler
doc promises that it'll work though - if it doesn't promise that,
optimizations or compiler upgrades or may break such an assumption.

Otherwise you just have to test for overflow a lot and react accordingly.

struct u_ninebit { unsigned int val:9; } is fine for unsigned arithmetic
though.

 

[Nate Eldredge]

If you are lucky, struct s_ninebit { signed int val:9; }". I.e. if your
program does not need to be portable, and your C implementation uses
saturation for bit fields. Don't depend on that unless the compiler
doc promises that it'll work though - if it doesn't promise that,
optimizations or compiler upgrades or may break such an assumption.

You'd have to be pretty lucky. What modern implementations use
saturation for bit fields? I don't know of any, though I admit my
experience is not particularly broad.

Otherwise you just have to test for overflow a lot and react accordingly.

That's what I'd recommend.

Note that a language like C++ that has operator overloading might make
this a lot more convenient.

struct u_ninebit { unsigned int val:9; } is fine for unsigned arithmetic
though.

In this case, as I understand it, arithmetic is guaranteed *not* to
saturate, but to wrap around on overflow instead.

 

[Tim Harig]

If you are lucky, struct s_ninebit { signed int val:9; }". I.e. if your
program does not need to be portable, and your C implementation uses
saturation for bit fields. Don't depend on that unless the compiler
doc promises that it'll work though - if it doesn't promise that,
optimizations or compiler upgrades or may break such an assumption.
Unwise.

Otherwise you just have to test for overflow a lot and react accordingly.

This could be error prone as it would be easy to miss a check and
depending how the checks/conversions are implented it could spread
unportable code throughout the code base (having do deal with endian
order, 1s vs 2s compliment, etc.).

I would think that it would be far better to write two translation
functions where implementations specific code would be stored.
Data values are translated to normal C types before any operations
take place. The arithmetic is done normally without having to deal
with any special conditions. Then when the operation is finished, the
C types are handed back to an implementations specific function which
handles overflow, endian issues, sign issues (1s vs 2s compliment), and
hands back the necessary 9-bit representations for storage. It would be
important, however, to keep operations as simple, atomic, single steps,
as performing multiple operations might proceed normally without regard
for the fact that an intermediate operation would have caused an overflow
in the 9-bit representation.

 

[Flash Gordon]

Unwise.

Agreed, especially as a compilers which do this are (I think)
exceedingly rare. Note that naturally purple with yellow polka dot
unicorns are also exceedingly rare.

This could be error prone as it would be easy to miss a check and
depending how the checks/conversions are implented it could spread
unportable code throughout the code base (having do deal with endian
order, 1s vs 2s compliment, etc.).

You don't have to deal with 1s vs 2s complement or endianness

int is /* guaranteed to be at least 16 bits when the OP only wants 9 bits */

/* do stuff */
if (i<-256)
i=-256;
else if (i>255)
i=255;

Of course, as someone else suggested, wrapping this in functions would
be a good thing. These would have to be functions for the basic
operations, i.e. add, sub, multiply (I think) to implement the OPs
requirements.

I would think that it would be far better to write two translation
functions where implementations specific code would be stored.

<snip>

There is NO implementation specific code required!

 

[Keith Thompson]

Agreed, especially as a compilers which do this are (I think)
exceedingly rare. Note that naturally purple with yellow polka dot
unicorns are also exceedingly rare.


You don't have to deal with 1s vs 2s complement or endianness

int is /* guaranteed to be at least 16 bits when the OP only wants 9 bits */

/* do stuff */
if (i<-256)
i=-256;
else if (i>255)
i=255;

This can fail if preceded by:
i = x * y;
where, for example, x and y are both equal to 255 (65025 > 32767).

But using long, which is guaranteed to be at least 32 bits and is more
than wide enough to hold the product of any two 9-bit nubmers, solves
this.

 

[BartC]

This can fail if preceded by:
i = x * y;
where, for example, x and y are both equal to 255 (65025 > 32767).

But using long, which is guaranteed to be at least 32 bits and is more
than wide enough to hold the product of any two 9-bit nubmers, solves
this.

We don't know exactly how the ALU will handle multiplication. Maybe the
result of 255x255 in 9 bits will be 1, the same as the bottom 9 bits of a
16-bit 255x255.

So I suspect it doesn't matter provided int's are at least 9 bits.

 

[Tim Harig]

You don't have to deal with 1s vs 2s complement or endianness [SNIP]
There is NO implementation specific code required!

I am assuming that the original poster, in modeling the his hardware
design, will at some point or another want to represent the binary
structure, not just the arithmatic values, of the data inside of the the
hardware that he is trying to simulate. This would be necessary, for
instance, to know what the I/O pins on a microcontroller would be when
outputing the result of a given calculation. The original poster may not
need this.

If this is the case, then it would be necessary to take into account how
the hypothetical processor represents values internally. The poster said
that he is simulating signed arithmetic; therefore, to know the physical
representation the compliment used to store negative numbers is important.
-20 in 16bit twos compliment big endian is 1111111111101100 whereas it
is 1000000000001010 stored in 16 bit 1s compliment big endian. A big
difference; especially, when trying to flatten the value to only 9 bits.

Endian with only a single extra bit over a byte may not make as much
difference; but, it still must be accounted for if one needs to know if one
wants to know how a section of memory from the hypothecial processor would
look like being sent from a serial shift register. This would be useful
while trying to debug an I2C transfer program for an MCU. The endianess
wouldn't make sense for only 9bits on the MCU but it could very well mean a
necessary byteswap on the little endian Intel 386 architecture.

The OP may very well not need these representations and my be very happy
only knowing the arithmatical results. But he didn't specify enough
information to know otherwise and I don't like to make assumptions.

 

[Keith Thompson]

We don't know exactly how the ALU will handle multiplication. Maybe
the result of 255x255 in 9 bits will be 1, the same as the bottom 9
bits of a 16-bit 255x255.

So I suspect it doesn't matter provided int's are at least 9 bits.

int is guaranteed to be at least 16 bits; more precisely, the
guaranteed range is at least -32767 .. +32767. Even if an
implementation has a 9-bit integer type, the "usual arithmetic
conversions" are performed on the operands of the "*" operator, so the
multiplication will take place in a type at least as wide as int.

If you attempt to compute 255 * 255, and int is only 16 bits, then the
behavior is undefined.

If you think the OP's requirements can be met without using a type
wider than 16 bits, I'd be interested in seeing some code. (You could
detect overflow before doing the operation, but that's hardly likely
to be easier than just using a wider type.)

 

[Tim Harig]

int is guaranteed to be at least 16 bits; more precisely, the
guaranteed range is at least -32767 .. +32767. Even if an
implementation has a 9-bit integer type, the "usual arithmetic
conversions" are performed on the operands of the "*" operator, so the
multiplication will take place in a type at least as wide as int.

That may all be true for C but it may not be true for the hardware that the
OP is trying to model. A 9bin microcontroller only has 9bits of space that
it can work with -- it cannot multiply in 16 bit space. It will overflow
if you try.

Most 8bit microprocessors do not even try to perform multiplication
directly because of the severe limitations. They may be loaded with
software which performs the actions necessary to multiply accress
registers for using BCD math; but, that wouldn't be relevant for somebody
trying to emulate the microprocessor for debugging.

 

[Hamiral]

Arturi a écrit :

Hi all,

what's the trick to perform 9 bit arithmetics in C? I am modeling a
hardware design and I need to perform signed 9bit arith with
saturation.

Any ideas??

Cheers

Why not representing your numbers with a struct ?

typedef struct int9_s {
unsigned char number;
unsigned char sign : 1;
} int9;

This way you can have numbers going from -255 to +255.
And then a set of arithmetic functions that take int9's as inputs.
Well, this way you don't really emulate 9bits arithmetics, but rather
arithmetics in the range -255 to +255, which may be different than what
you asked for.
Anyway, I think I would do it like this because it seems to be the
easiest way...

Ham

 

[Tim Harig]

That may all be true for C but it may not be true for the hardware that the

OP is trying to model. A 9bin microcontroller only has 9bits of space that
it can work with -- it cannot multiply in 16 bit space. It will overflow
if you try.

Or in this case, saturate and clamp high at 255.

 

[Keith Thompson]

That may all be true for C but it may not be true for the hardware that the
OP is trying to model. A 9bin microcontroller only has 9bits of space that
it can work with -- it cannot multiply in 16 bit space. It will overflow
if you try.

Most 8bit microprocessors do not even try to perform multiplication
directly because of the severe limitations. They may be loaded with
software which performs the actions necessary to multiply accress
registers for using BCD math; but, that wouldn't be relevant for somebody
trying to emulate the microprocessor for debugging.

If so, the OP is asking in the wrong place.

 

[Tim Harig]

-20 in 16bit twos compliment big endian is 1111111111101100 whereas it

is 1000000000001010 stored in 16 bit 1s compliment big endian. A big

err, 1111111111101100 vs 1000000000001100

 

[Tim Harig]

If so, the OP is asking in the wrong place.

He wants a program written in C on his computer to work like his hardware.
Those who develop MPU/MCU/DSP based applications don't necessarily know
anything about C. C programmers don't necessarily know anything about
MPU/MCU/DSPs or even binary manipulation. Which group he should post to is
a judgement call. Maybe he figured that since he knows about his hardware
but not much about C that a group about C might be of some help.
Maybe he was right or maybe he was wrong. Maybe there was no perfect
answer so he went with the best solution he could find. maybe he is
38.12394793% right. Who knows?

 

[Flash Gordon]

This can fail if preceded by:
i = x * y;
where, for example, x and y are both equal to 255 (65025 > 32767).

But using long, which is guaranteed to be at least 32 bits and is more
than wide enough to hold the product of any two 9-bit nubmers, solves
this.

Yes, you are correct, I should have thought more carefully.

 

[Flash Gordon]

Arturi writes:
what's the trick to perform 9 bit arithmetics in C? I am modeling
a hardware design and I need to perform signed 9bit arith with
saturation.

You don't have to deal with 1s vs 2s complement or endianness [SNIP]
There is NO implementation specific code required!

I am assuming that the original poster, in modeling the his hardware
design, will at some point or another want to represent the binary
structure, not just the arithmatic values, of the data inside of the the
hardware that he is trying to simulate. This would be necessary, for
instance, to know what the I/O pins on a microcontroller would be when
outputing the result of a given calculation. The original poster may not
need this.

This still does not need any implementation specific code. You also
don't have to deal with it for the arithmetic, if you need it at all
just write two functions to do the conversion between the targets
representation and the native C representation.

If this is the case, then it would be necessary to take into account how
the hypothetical processor represents values internally. The poster said
that he is simulating signed arithmetic; therefore, to know the physical
representation the compliment used to store negative numbers is important.
-20 in 16bit twos compliment big endian is 1111111111101100 whereas it
is 1000000000001010 stored in 16 bit 1s compliment big endian. A big
difference; especially, when trying to flatten the value to only 9 bits.

It may or may not be important for some other requirements, but it does
not require implementation specific code.

Endian with only a single extra bit over a byte may not make as much
difference; but, it still must be accounted for if one needs to know if one
wants to know how a section of memory from the hypothecial processor would
look like being sent from a serial shift register. This would be useful
while trying to debug an I2C transfer program for an MCU. The endianess
wouldn't make sense for only 9bits on the MCU but it could very well mean a
necessary byteswap on the little endian Intel 386 architecture.

None of which requires any implementation specific code.

The OP may very well not need these representations and my be very happy
only knowing the arithmatical results. But he didn't specify enough
information to know otherwise and I don't like to make assumptions.

None of the things you have raised require any implementation specific
code. All of them require application specific code.

 

[Tim Harig]

Tim Harig wrote:
I would think that it would be far better to write two translation
functions where implementations specific code would be stored.
Data values are translated to normal C types before any operations
take place. The arithmetic is done normally without having to deal
with any special conditions. Then when the operation is finished, the
C types are handed back to an implementations specific function which
handles overflow, endian issues, sign issues (1s vs 2s compliment), and
hands back the necessary 9-bit representations for storage. It would be
important, however, to keep operations as simple, atomic, single steps,
as performing multiple operations might proceed normally without regard
for the fact that an intermediate operation would have caused an overflow
in the 9-bit representation.

You don't have to deal with 1s vs 2s complement or endianness [SNIP]
There is NO implementation specific code required!

I am assuming that the original poster, in modeling the his hardware
design, will at some point or another want to represent the binary
structure, not just the arithmatic values, of the data inside of the the
hardware that he is trying to simulate. This would be necessary, for
instance, to know what the I/O pins on a microcontroller would be when
outputing the result of a given calculation. The original poster may not
need this.

This still does not need any implementation specific code. You also
don't have to deal with it for the arithmetic, if you need it at all
just write two functions to do the conversion between the targets
representation and the native C representation.

Having conversion functions is exactly what I suggested above.
The conversion to whatever his virtual machine uses would be application
dependant based on his virtual machine. However, Making the conversion
from whatever format is used by his computer will be different based upon
the scheme that his computer/compiler uses. That makes the conversion
implmentation dependant based on his computer architecture. The process
for down casting a 2s complement number down to whatever 9bit format then is
different then the process of downcasting from a 1s complement to the 9bit
format in whatever compliment.

Furthermore, if the computer uses ones complement, then the sign bit
may need to be taken from different places to perform the 9bit casing
depending on the actual size of the C types which are not defined by
standard which also suggests the need for implementation specific code.

None of which requires any implementation specific code.

If his computer is big endian then he will not have to change anything. If
his computer is litte endian then he will have to swap the extra bit
forward during conversion to make the simulated memory layout match
that of the virtual hardare when modeling the virtual hardware's memory.
Otherise, making a memory dump of the virtual hardware will be inaccurate
as the most significant bit will follow the rest of the bits when
being dumped. Once again, this would be different depending on the
processor architecture of the OPs processor; and therefore, implementation
dependant.

Endedness would not have made any difference if we were dealing with
a virtual architecture less then or equal to 8 bits. Had it been less
then or equal to 8 bits; then, it would instead be important to know that
some architectures cannot write on odd byte boundries and two represented
numbers for the virtual machine would need to be added together within
the hosting archetecture to assure that one does not try to write to
an odd byte and to dump the virtual memory without zero bytes between
the numbers. This would have been a problem using 68000 based computers.
The bottom line is that care is required when working with any binary
data if one needs it to be portable across computers.

None of the things you have raised require any implementation specific
code. All of them require application specific code.

Application specific code is required in determining the parameters of the
virtual machine; but, implementation specific code is required dependant
upon the internal representation of numbers on the computer architecture
and compiler of the hosting computer. These differences need to be taken
into account whenever working with binary data if the user wishes to be
cross platform. It is true, that the methods will always be the same if
the user can assume that the hosting computer is a little endian, 2s
complement computer with a compiler that uses an int size of 16 bits.
If he cannot, then he needs to consider other possibilities. I always
try to make as few assumptions as possible. I have worked under conditions
where these assumptions are invalid.

The good news is that all of these variables only need to be considered
for two functions: the one which converts from the virtual format to
the native format and the one which converts from the native format to
the virtual format. But do not be fooled into thinking that these
functions can be the same for all hosting computers.

 

[Ben Bacarisse]

Tim Harig wrote:
I would think that it would be far better to write two translation
functions where implementations specific code would be stored.
Data values are translated to normal C types before any operations
take place. The arithmetic is done normally without having to deal
with any special conditions. Then when the operation is finished, the
C types are handed back to an implementations specific function which
handles overflow, endian issues, sign issues (1s vs 2s compliment), and
hands back the necessary 9-bit representations for storage. It would be
important, however, to keep operations as simple, atomic, single steps,
as performing multiple operations might proceed normally without regard
for the fact that an intermediate operation would have caused an overflow
in the 9-bit representation.
You don't have to deal with 1s vs 2s complement or endianness
[SNIP]
There is NO implementation specific code required!
I am assuming that the original poster, in modeling the his hardware
design, will at some point or another want to represent the binary
structure, not just the arithmatic values, of the data inside of the the
hardware that he is trying to simulate. This would be necessary, for
instance, to know what the I/O pins on a microcontroller would be when
outputing the result of a given calculation. The original poster may not
need this.

This still does not need any implementation specific code. You also
don't have to deal with it for the arithmetic, if you need it at all
just write two functions to do the conversion between the targets
representation and the native C representation.

Having conversion functions is exactly what I suggested above.
The conversion to whatever his virtual machine uses would be application
dependant based on his virtual machine. However, Making the conversion
from whatever format is used by his computer will be different based upon
the scheme that his computer/compiler uses. That makes the conversion
implmentation dependant based on his computer architecture. The process
for down casting a 2s complement number down to whatever 9bit format then is
different then the process of downcasting from a 1s complement to the 9bit
format in whatever compliment.

Furthermore, if the computer uses ones complement, then the sign bit
may need to be taken from different places to perform the 9bit casing
depending on the actual size of the C types which are not defined by
standard which also suggests the need for implementation specific code.

None of which requires any implementation specific code.

If his computer is big endian then he will not have to change anything. If
his computer is litte endian then he will have to swap the extra bit
forward during conversion to make the simulated memory layout match
that of the virtual hardare when modeling the virtual hardware's memory.
Otherise, making a memory dump of the virtual hardware will be inaccurate
as the most significant bit will follow the rest of the bits when
being dumped. Once again, this would be different depending on the
processor architecture of the OPs processor; and therefore, implementation
dependant.

There may be a terminology problem here. I think what Flash Gordon is
saying is that there does not appear to be any reason why the code
could not be written is such a way as to entirely portable.
I.e. there would be no need to change the source when moving from a
big- to little-endian machine. Let me illustrate where the problem
might lie.

If I choose to represent 9-bit signed values as long ints in the range
-256 to 255. Lets also assume the simulation requores that these
9-bit int look like 2's compliment numbers (no matter how they may
actually be held in the simulation). I can dump a single memory
location (x) like this:

printf("%d%02x", x < 0, (0x100 + x) % 0x100);

On all conforming C implementation, I'll get the same result for all
values of x in the target range. Exactly what happens in the
arithmetic varies from implementation to implementation, but the
result will always be the same.

Had I written it as:

printf("%d%02x", x < 0, x & 0xff);

then the code is implementation dependent in the sense the Flash
Gordon was saying can be avoided. It will not work on sign and
magnitude machines, for example. I could have made matters worse by
getting sign bit by some bit operation.

Had I chosen to use a char pointer to access the memory, then endian
issues would have com up as well. The point is that all
implementation issue can be avoided in this case to give entirely
portable code.

Endedness would not have made any difference if we were dealing with
a virtual architecture less then or equal to 8 bits. Had it been less
then or equal to 8 bits; then, it would instead be important to know that
some architectures cannot write on odd byte boundries and two represented
numbers for the virtual machine would need to be added together within
the hosting archetecture to assure that one does not try to write to
an odd byte and to dump the virtual memory without zero bytes between
the numbers. This would have been a problem using 68000 based computers.
The bottom line is that care is required when working with any binary
data if one needs it to be portable across computers.


Application specific code is required in determining the parameters of the
virtual machine; but, implementation specific code is required dependant
upon the internal representation of numbers on the computer architecture
and compiler of the hosting computer. These differences need to be taken
into account whenever working with binary data if the user wishes to be
cross platform. It is true, that the methods will always be the same if
the user can assume that the hosting computer is a little endian, 2s
complement computer with a compiler that uses an int size of 16 bits.
If he cannot, then he needs to consider other possibilities. I always
try to make as few assumptions as possible. I have worked under conditions
where these assumptions are invalid.

Unless there is some devious problem to do with the OP's question, all
assumptions about the hosting computer can be avoided.

The good news is that all of these variables only need to be considered
for two functions: the one which converts from the virtual format to
the native format and the one which converts from the native format to
the virtual format. But do not be fooled into thinking that these
functions can be the same for all hosting computers.

I can't see a compelling reason for them *not* to be the same. Of
course a bad choice of "virtual format" might give you no end of
trouble, but if you get that right, I can't see why the code could not
be portable.