I've been talking about portable C programming lately, and I've
claimed that I write fully-portable code. Many people here contested
this claim, some more rudely than others, so instead of trash-talking
back and forth I'm going to actually give an example of the way I
code.

In my most recent embedded project, there was a severe memory
restriction. I had to store in memory the state of 42 individual
LED's. Each LED could have one of three states. To use the least
amount of memory possible for each LED, I thought I'd go with the
following strategy:

   * Use three bits per LED. 00 = Off. 01 = Red. 10 = Unused. 11 =
Green.

I decided to go about writing a "module", a C source and header file
couple that would handle this tight memory access and provide a nice,
clean, easy-to-use interface. The module would need two pieces of
information from the programmer:

    * The amount of combinations (i.e. 3 for my LEDs' states)
    * The amount of chunks (i.e. 42 because I've 42 individual LED's)

From there, it would handle all the data accessing, both reading and
writing. All the programmer has to do is invoke "GetChunk" and
"SetChunk".

In starting out to write this module, I knew I wanted it to be as
portable as possible. I wanted it to work on machines that have an 8-
Bit byte. Also those funky old machines that have a 9-Bit byte. Also
supercomputers that have a 64-Bit byte.

First off, I started with a header file to provide an interface. I
refer to the little 3-Bit chunks of memory as a "chunk", and so the
functions are "SetChunk" and "GetChunk". (Of course you can set the
chunk size bigger or smaller than 3 bits).

Here's the header file:

/* ------------------------ Begin Header File:  data_acc.h
------------------------------ */
#ifndef H__DATA_ACC
#define H__DATA_ACC

#include <stdint.h>

void SetChunk(uint_fast16_t const i, uint_fast8_t const state);
uint_fast8_t GetChunk(uint_fast16_t const i);

void SetEntireDataAllZeroes(void);
void SetEntireDataAllOnes(void);

#endif
/* ------------------------ End Header File:  data_acc.h
------------------------------ */


Before I show the source code, I'm going to mention a complication.
Let's take a canonical system such as an Intel PC that has an 8-Bit
byte. If we were to use 3 bits per LED, then we'd be able to store 2
LED's in one byte and we'd have 2 bits left over (i.e. 2(3) + 2 = 8).
Well, instead of discarding those bits, what my code does is it takes
the last 2 bits from the previous byte in conjunction with the 1st bit
of the next byte. No bits are wasted on any system, regardless of the
amount of bits in a byte or the amount of bits per "chunk".

Now before I show the source file, I have to tell you about the two
constants that are required from the programmer:

    QUANTITY_CHUNKS    (e.g. This is 42 for the 42 LED's)
    BITS_PER_CHUNK      (e.g. This is 2 because I've 2 bits per LED,
e.g. 01 = Red)

These two constants shall be defined in a file called
"data_acc_specs.h". Here's a sample:

    #define QUANTITY_CHUNKS 42u
    #define BITS_PER_CHUNK 3u

How the source code works is as follows. Internally, it has the
concept of a "chunk pointer", i.e. a data type that gives it all the
information it needs to locate a specific chunk in memory. The chunk
pointer consists of two things:
    * The address of the byte in which the first bit resides
    * The index of the bit in that byte

When you invoke GetChunk for instance, it will convert the index of a
chunk to a "chunk pointer", and this chunk pointer will give it the
information it needs to locate and read the relevant chunk.

Here's the source code:

/* ------------------------ Begin Source File:  data_acc.c
------------------------------ */
#include "data_acc.h"
#include "data_acc_specs.h"

#include <string.h>   /* memset */
#include <limits.h>   /* CHAR_BIT */
#include <assert.h>


#define TOTAL_BITS_NEEDED (QUANTITY_CHUNKS * BITS_PER_CHUNK)

#define BYTES_NEEDED (TOTAL_BITS_NEEDED / CHAR_BIT + !!
(TOTAL_BITS_NEEDED % CHAR_BIT))

#define BITS_ALL_ONES(x) ((1u << (x)) - 1u)

#define CHUNK_ALL_ONES (BITS_ALL_ONES(BITS_PER_CHUNK))


static char unsigned data[BYTES_NEEDED];    /* Raw memory for storing
chunks */


typedef struct ChunkAddress {

    char unsigned *pbyte;
    uint_fast8_t i_bit;

} ChunkAddress;


static ChunkAddress GetChunkAddress(uint_fast16_t const chunk)
{
#   define i_bit_in_entire_data (chunk * BITS_PER_CHUNK)

#   define i_byte (i_bit_in_entire_data / CHAR_BIT)

    ChunkAddress addrs;

    assert(chunk < QUANTITY_CHUNKS);

    addrs.pbyte = data + i_byte;
    addrs.i_bit = i_bit_in_entire_data % CHAR_BIT;

    return addrs;

#   undef i_bit_in_entire_data
#   undef i_byte
}


uint_fast8_t GetChunk(uint_fast16_t const i)
{
    ChunkAddress const addrs = GetChunkAddress(i);

    char unsigned x = *addrs.pbyte;

    assert(i < QUANTITY_CHUNKS);

    x >>= addrs.i_bit;

#   if CHAR_BIT % BITS_PER_CHUNK   || !defined(NDEBUG) /* Chunk can
spill into next byte */

    if (addrs.i_bit + BITS_PER_CHUNK > CHAR_BIT)  /* Has spilt into
next byte */
    {
#       define bits_in_current_byte (CHAR_BIT - addrs.i_bit)
#       define bits_in_next_byte    (BITS_PER_CHUNK -
bits_in_current_byte)

         char unsigned y = addrs.pbyte[1];

         y &= BITS_ALL_ONES(bits_in_next_byte);

         y <<= bits_in_current_byte;

#       undef bits_in_current_byte
#       undef bits_in_next_byte

        return x|y;
    }

#   endif

    return x & CHUNK_ALL_ONES;
}


void SetChunk(uint_fast16_t const chunk, uint_fast8_t const cs)
{
    ChunkAddress const addrs = GetChunkAddress(chunk);

    char unsigned x = *addrs.pbyte;

    /* ---- First clear the chunk bits ---- */

    x &= ~(CHUNK_ALL_ONES << addrs.i_bit);


    /* Now OR the actual chunk shifted to the correct place */

    x |= (unsigned)cs << addrs.i_bit;

    *addrs.pbyte = (char unsigned)x; /* Truncation warning cast */


#   if CHAR_BIT % BITS_PER_CHUNK || !defined(NDEBUG) /* Chunk can
spill into next byte */

    if (addrs.i_bit + BITS_PER_CHUNK   > CHAR_BIT)  /* Has spilt into
next byte */
    {
#       define bits_in_current_byte (CHAR_BIT - addrs.i_bit)
#       define bits_in_next_byte (BITS_PER_CHUNK -
bits_in_current_byte)

        char unsigned y = addrs.pbyte[1];

        /* ---- First clear the chunk bits ---- */

        y &= ~BITS_ALL_ONES(bits_in_next_byte);

        /* ---- Now OR with chunk bits ---- */

        y |= cs >> bits_in_current_byte;

#       undef bits_in_current_byte
#       undef bits_in_next_byte

        addrs.pbyte[1] = (char unsigned)y;  /* Cast to suppress
truncation warning */
    }

#   endif

}

void SetEntireDataAllOnes(void) { memset(data,-1,sizeof data); }

void SetEntireDataAllZeroes(void) { memset(data,0,sizeof data); }

/* ------------------------ End Source File:  data_acc.c
------------------------------ */



Of course, at the end of all that, you'll want to test it to see if it
actually works, so here's a sample tester:



/* ------------------------ Begin Source File:  main.c
------------------------------ */
#include <stdio.h>
#include <stdint.h>

#include "data_acc.h"

uint_fast8_t fat_array[42];

int main(void)
{
    uint_fast16_t i;

    uint_fast8_t chunk_value = 0;


    puts("Filling the fat array...\n");


    for (i = 0; 42 != i; ++i)
    {
        fat_array[i] = chunk_value++;

        chunk_value %= 4;
    }


    puts("Filling the skinny array...\n");


    for (i = 0; 42 != i; ++i)
    {
        SetChunk(i,fat_array[i]);
    }


    puts("Comparing the two...\n");


    for (i = 0; 42 != i; ++i)
    {
        if (GetChunk(i) == fat_array[i])
            printf("Equal. Value = %u\n",(unsigned)fat_array[i]);
        else
            puts("ERROR");
    }

    return 0;
}
/* ------------------------  End Source File:  main.c
------------------------------ */

So that's it.

I've written this post to show an example of fully-portable code, that
is, code that will behave exactly as intended on every conceivable
implementation of the C89 standard.

Of course, people will give examples of more complicated algorithms,
things like encryption, and I will admit that these things are more
complex to implement portably, but not impossible.

In C, the "unsigned char" type has no padding bits and thus it allows
you full access to a contiguous piece of memory, and therefore it can
be used to do whatever the you want with memory. At times, this can be
the key to implementing fully-portable code.

If you're working with a machine such as an Intel PC and you're
writing an encryption algorithm, then it probably is more efficient to
make assumptions about the size of a byte, about the lack of padding
in integer types -- and these non-portable assumptions will probably
lead to more efficient assembler, but with that said, portable
programming in C is not impossible.

So far, I've had a few people contest my claim of writing fully-
portable C code. Most of these people also took the opportunity to
attack me personally instead of focusing on the discussion. I did not
write this thread for those people; I wrote this thread in the hope of
enlightening the friendly, polite people about fully-portable C
programming, and also to rest any doubts they had about me not being
capable of it.

And lastly, but certainly not least, I'm not infallible. I've checked
over the above code a few times, but I haven't actually sat down and
gone thru it with a fine-tooth comb. If there's any errors or
oversights, please feel free to (politely) point them out to me.

Let's hope this doesn't start a flame.

On May 12, 11:10=A0pm, Tom=E1s =D3 h=C9ilidhe <t...@lavabit.com> wrote:

> First off, I started with a header file to provide an interface. I
> refer to the little 3-Bit chunks of memory as a "chunk", and so the
> functions are "SetChunk" and "GetChunk". (Of course you can set the
> chunk size bigger or smaller than 3 bits).


Both of those 3's should be 2's. (I got mixed up between using 2 bits
per LED and having 3 different combinations).


> =A0 =A0 #define QUANTITY_CHUNKS 42u
> =A0 =A0 #define BITS_PER_CHUNK 3u


That 3 again should be a 2, but you can compile it as is and it still
works. In fact, setting it to 3 lets you test out the "overflow"
functionality whereby a chunk can spill into the next adjacent byte.

Tomás Ó hÉilidhe wrote:

Snip...

> In my most recent embedded project, there was a severe memory
> restriction. 

Then do it in 8 lines of assembly code and
be done with it.

Snip...

> Let's hope this doesn't start a flame.

Sorry...

Tom=E1s =D3 h=C9ilidhe wrote:

> I've been talking about portable C programming lately, and I've
> claimed that I write fully-portable code. Many people here contested
> this claim, some more rudely than others, so instead of trash-talking
> back and forth I'm going to actually give an example of the way I
> code.

It is a pleasure to see how you are standing for your words without=20
loosing your face. Good job, sir.

>=20
> In my most recent embedded project, there was a severe memory
> restriction. I had to store in memory the state of 42 individual
> LED's. Each LED could have one of three states.

Hence there is a minimum of 67 bits. But this will require heavy weight=20
arithmetics.

> To use the least
> amount of memory possible for each LED, I thought I'd go with the
> following strategy:
>=20
> * Use three bits per LED. 00 =3D Off. 01 =3D Red. 10 =3D Unused. 11 =3D=

> Green.

:))))

Combine the state of five leds into one byte. That totals to eight bytes =

plus four bits for the remaining two leds =3D 68 bits.

[...]


> Of course, people will give examples of more complicated algorithms,
> things like encryption, and I will admit that these things are more
> complex to implement portably, but not impossible.

Being portable is not an ultimate goal by itself. The goal is get your=20
bills payed; the portability is only one of the tools in your toolbox.

> In C, the "unsigned char" type has no padding bits and thus it allows
> you full access to a contiguous piece of memory,

[...]

How can you preach that boring stuff? Get a life :)

> So far, I've had a few people contest my claim of writing fully-
> portable C code.

Really? I thought who would have care :)

> Most of these people also took the opportunity to
> attack me personally instead of focusing on the discussion.

That's the whole point of the newsgroups: proving that your opponent is=20
an idiot. The more technical you are, the more damage you are making :)

> I did not
> write this thread for those people;

Oh, sure, yes you did :)

> I wrote this thread in the hope of
> enlightening the friendly, polite people about fully-portable C
> programming,

Wow! Tears in my eyes.

> and also to rest any doubts they had about me not being
> capable of it.

This is closer to the truth.

> And lastly, but certainly not least, I'm not infallible. I've checked
> over the above code a few times, but I haven't actually sat down and
> gone thru it with a fine-tooth comb. If there's any errors or
> oversights, please feel free to (politely) point them out to me.

This is not an excuse. I am prepared to see how the lions and tigers=20
will tear you apart :)


> Let's hope this doesn't start a flame.


Let's hope this will start a good flame!



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

> > Most of these people also took the opportunity to
> > attack me personally instead of focusing on the discussion.

Nothing personal, just institional.

>
> That's the whole point of the newsgroups: proving that your opponent is
> an idiot. The more technical you are, the more damage you are making :)

He claims to be the cream of the crop in his country/college.  I
really question the educational system over there, wherever it is.

Vladimir Vassilevsky wrote:
> 
> 
> Tomás Ó hÉilidhe wrote:
> 

<snip>

>> So far, I've had a few people contest my claim of writing fully-
>> portable C code.
> 
> Really? I thought who would have care :)
> 
>> Most of these people also took the opportunity to
>> attack me personally instead of focusing on the discussion.
> 
> That's the whole point of the newsgroups: proving that your opponent is 
> an idiot. The more technical you are, the more damage you are making :)
> 
>> I did not
>> write this thread for those people;
> 
> Oh, sure, yes you did :)
> 
>> I wrote this thread in the hope of
>> enlightening the friendly, polite people about fully-portable C
>> programming,
> 
> Wow! Tears in my eyes.
> 
>> and also to rest any doubts they had about me not being
>> capable of it.
> 
> This is closer to the truth.
> 
>> And lastly, but certainly not least, I'm not infallible. I've checked
>> over the above code a few times, but I haven't actually sat down and
>> gone thru it with a fine-tooth comb. If there's any errors or
>> oversights, please feel free to (politely) point them out to me.
> 
> This is not an excuse. I am prepared to see how the lions and tigers 
> will tear you apart :)
> 
> 
>> Let's hope this doesn't start a flame.
> 
> 
> Let's hope this will start a good flame!
> 

Now here is someone who truly understands the purpose of Usenet!


I don't have time to justice to the post now - perhaps later.  But I can 
give a couple of points:

Portability between programmers, and between the same programmer six 
months after writing the code, is vastly more important than 
"portability" between targets with weird numbers of bits per character.

Thus the correct *portable* way to write this code is to assume that 
CHAR_BIT is 8.  You have a little #if and #error at the start to check 
that assumption.  Then your code is much smaller, much clearer, and 
probably much more efficient in its generated object code, as it cuts 
out much of the junk.  If you have to use this same module on a target 
with other CHAR_BIT values, you can write a modified version then.


I think my claim was:

"I haven't seem much indication from your posts that you can write 
legible C code at all, never mind "fully portable" code (to the extent 
that such a thing really exists)."


Given that monstrosity of unnecessary preprocessor gymnastics (and it 
certainly doesn't help that you miswrite your directives by separating 
the # from the keyword), I stand by that claim.

Vladimir Vassilevsky <a...@hotmail.com> writes:
> 
> Tom=E1s =D3 h=C9ilidhe wrote:
> 
> > I've been talking about portable C programming lately, and I've
> > claimed that I write fully-portable code. Many people here contested
> > this claim, some more rudely than others, so instead of trash-talking
> > back and forth I'm going to actually give an example of the way I
> > code.
> 
> It is a pleasure to see how you are standing for your words without
> loosing your face. Good job, sir.
> 
> >
> > In my most recent embedded project, there was a severe memory
> > restriction. I had to store in memory the state of 42 individual
> > LED's. Each LED could have one of three states.
> 
> Hence there is a minimum of 67 bits. But this will require heavy weight
> arithmetics.
> 
> > To use the least
> > amount of memory possible for each LED, I thought I'd go with the
> > following strategy:
> >
> > * Use three bits per LED. 00 = Off. 01 = Red. 10 = Unused. 11 =
> > Green.
> 
> :))))
> 
> Combine the state of five leds into one byte. That totals to eight bytes
> plus four bits for the remaining two leds = 68 bits.
> [...]

Somebody is using strange arithmetic.  At a minimum, using the
state encoding prescribed, you need two bits per LED.  Assuming
8-bit bytes, four LED's states can be packed in one byte.  The
states for 42 LEDs can then be packed in 11 bytes or 88 bits.

> > Of course, people will give examples of more complicated algorithms,
> > things like encryption, and I will admit that these things are more
> > complex to implement portably, but not impossible.
> 
> Being portable is not an ultimate goal by itself. The goal is get your
> bills payed; the portability is only one of the tools in your toolbox.
> 
> > In C, the "unsigned char" type has no padding bits and thus it allows
> > you full access to a contiguous piece of memory,
> 
> [...]
> 
> How can you preach that boring stuff? Get a life :)
> 
> > So far, I've had a few people contest my claim of writing fully-
> > portable C code.
> 
> Really? I thought who would have care :)
> 
> > Most of these people also took the opportunity to
> > attack me personally instead of focusing on the discussion.
> 
> That's the whole point of the newsgroups: proving that your opponent is
> an idiot. The more technical you are, the more damage you are making :)
> 
> > I did not
> > write this thread for those people;
> 
> Oh, sure, yes you did :)
> 
> > I wrote this thread in the hope of
> > enlightening the friendly, polite people about fully-portable C
> > programming,
> 
> Wow! Tears in my eyes.
> 
> > and also to rest any doubts they had about me not being
> > capable of it.
> 
> This is closer to the truth.
> 
> > And lastly, but certainly not least, I'm not infallible. I've checked
> > over the above code a few times, but I haven't actually sat down and
> > gone thru it with a fine-tooth comb. If there's any errors or
> > oversights, please feel free to (politely) point them out to me.
> 
> This is not an excuse. I am prepared to see how the lions and tigers
> will tear you apart :)
> 
> 
> > Let's hope this doesn't start a flame.
> 
> 
> Let's hope this will start a good flame!

Everett M. Greene wrote:

> Vladimir Vassilevsky <a...@hotmail.com> writes:
> 
>>Tom=E1s =D3 h=C9ilidhe wrote:
>>
>>>In my most recent embedded project, there was a severe memory
>>>restriction. I had to store in memory the state of 42 individual
>>>LED's. Each LED could have one of three states.
>>
>>Hence there is a minimum of 67 bits. But this will require heavy weight
>>arithmetics.
>>
>>
>>>To use the least
>>>amount of memory possible for each LED, I thought I'd go with the
>>>following strategy:
>>>
>>>* Use three bits per LED. 00 = Off. 01 = Red. 10 = Unused. 11 =
>>>Green.
>>
>>:))))
>>
>>Combine the state of five leds into one byte. That totals to eight bytes
>>plus four bits for the remaining two leds = 68 bits.
>>[...]
> 
> 
> Somebody is using strange arithmetic.  At a minimum, using the
> state encoding prescribed, you need two bits per LED.

3^5 = 243. Hence the state of five LEDs can be packed into one byte.

>  Assuming
> 8-bit bytes, four LED's states can be packed in one byte.  The
> states for 42 LEDs can then be packed in 11 bytes or 88 bits.

But this is very dull.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On May 13, 10:08=A0am, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:
> Everett M. Greene wrote:
> > Vladimir Vassilevsky <antispam_bo...@hotmail.com> writes:
>
> >>Tom=3DE1s =3DD3 h=3DC9ilidhe wrote:
>
> >>>In my most recent embedded project, there was a severe memory
> >>>restriction. I had to store in memory the state of 42 individual
> >>>LED's. Each LED could have one of three states.
>
> >>Hence there is a minimum of 67 bits. But this will require heavy weight
> >>arithmetics.
>
> >>>To use the least
> >>>amount of memory possible for each LED, I thought I'd go with the
> >>>following strategy:
>
> >>>* Use three bits per LED. 00 =3D Off. 01 =3D Red. 10 =3D Unused. 11 =3D=

> >>>Green.
>
> >>:))))
>
> >>Combine the state of five leds into one byte. That totals to eight bytes=

> >>plus four bits for the remaining two leds =3D 68 bits.
> >>[...]
>
> > Somebody is using strange arithmetic. =A0At a minimum, using the
> > state encoding prescribed, you need two bits per LED.
>
> 3^5 =3D 243. Hence the state of five LEDs can be packed into one byte.
>
> > =A0Assuming
> > 8-bit bytes, four LED's states can be packed in one byte. =A0The
> > states for 42 LEDs can then be packed in 11 bytes or 88 bits.
>
> But this is very dull.
>

Even if the code is perfect, it's lots of overhead to save a few
bytes.  All these discussions of saving a few pins and bytes are just
meaningless.

On May 13, 12:07=A0am, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:

> > In my most recent embedded project, there was a severe memory
> > restriction. I had to store in memory the state of 42 individual
> > LED's. Each LED could have one of three states.
>
>
> Hence there is a minimum of 67 bits. But this will require heavy weight
> arithmetics.


More machine code also, and slower machine code at that.

Let me see...

3 combinations per LED. If I wanted the maximum efficient tight usage
of memory (forgetting about the memory consumed by the sub routines,
of course), then I'd need to find a multiple of 3 that is exactly
equal to 2 ^ x. (where x can be any integer). I don't think there is
such a number... is there? And if there is then it's HUGE, way too big
for playing around with 42 chunks.

Of course there's other ways of doing that "leave a few bits over"
though.