Memory-reversal Game

[Frederick Gotham]

I was intrigued by someone the other day who posted regarding methods of
"mirror-imaging" the bits in a byte. I thought it might be interesting to
write a fully-portable algorithm for mirror-imaging (i.e. reversing) an
entire chunk of memory, and making the algorithm as fast as possible (yes,
I realise it may be faster on some machines than on others, but still, one
can aim for pretty high average efficiency across the board.)

Anyway, here's my latest code, feel free to tamper. I haven't gone through
it with a fine-tooth comb, so it might contain a bug or two. The method it
uses for reversing bits in a byte is based on the code that looked
something like:

| ((unsigned)val & 128) >7
| ((unsigned)val & 64) >6

Here it is:

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>

/* The following macro sets a specified
sole bit index. (It would be better
to perform the assertion using IMAX_BITS
rather than sizeof(unsigned)*CHAR_BIT).
*/

#define ISOLATE_BIT(index) (\
assert((index) < sizeof(unsigned)*CHAR_BIT), \
1U << (index) )

/* The next macro gives us the reversed bit index,
e.g. for 8-Bit bytes:

0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
*/

#define REVERSAL_BIT_POSITION(index) (\
assert((index) < CHAR_BIT), \
CHAR_BIT-1 - (index) )
char unsigned ByteReversal(char unsigned val)
{
unsigned index, reversal = 0;

/* Deal with shifting to the left first. */

for(index = 0; index != CHAR_BIT/2; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))
<< REVERSAL_BIT_POSITION(index) - index;
}

/* Now deal with shifting to the right. */

for(; index != CHAR_BIT; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))

>index - REVERSAL_BIT_POSITION(index);

}

return reversal;
}

void ReverseMemory(void *const pv,size_t const quantity_bytes)
{
int const assert_dummy = (assert(!!pv),0);

char unsigned *p = pv,
*q = p + (quantity_bytes - 1);

for( ; q p; ++p, --q)
{
unsigned const temp = ByteReversal(*p);
*p = ByteReversal(*q);
*q = temp;
}
}

int main(void)
{
unsigned arr[64] = {0,1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63};

unsigned const *p, *const q = arr + sizeof arr/sizeof*arr;

p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");
}

--

Frederick Gotham

[Aman JIANG]

Frederick Gotham wrote:

I was intrigued by someone the other day who posted regarding methods of
"mirror-imaging" the bits in a byte. I thought it might be interesting to
write a fully-portable algorithm for mirror-imaging (i.e. reversing) an
entire chunk of memory, and making the algorithm as fast as possible (yes,
I realise it may be faster on some machines than on others, but still, one
can aim for pretty high average efficiency across the board.)

Anyway, here's my latest code, feel free to tamper. I haven't gone through
it with a fine-tooth comb, so it might contain a bug or two. The method it
uses for reversing bits in a byte is based on the code that looked
something like:

| ((unsigned)val & 128) >7
| ((unsigned)val & 64) >6

Here it is:

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>

/* The following macro sets a specified
sole bit index. (It would be better
to perform the assertion using IMAX_BITS
rather than sizeof(unsigned)*CHAR_BIT).
*/

#define ISOLATE_BIT(index) (\
assert((index) < sizeof(unsigned)*CHAR_BIT), \
1U << (index) )

/* The next macro gives us the reversed bit index,
e.g. for 8-Bit bytes:

0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
*/

#define REVERSAL_BIT_POSITION(index) (\
assert((index) < CHAR_BIT), \
CHAR_BIT-1 - (index) )
char unsigned ByteReversal(char unsigned val)
{
unsigned index, reversal = 0;

/* Deal with shifting to the left first. */

for(index = 0; index != CHAR_BIT/2; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))
<< REVERSAL_BIT_POSITION(index) - index;
}

/* Now deal with shifting to the right. */

for(; index != CHAR_BIT; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))

>index - REVERSAL_BIT_POSITION(index);

}

return reversal;
}

void ReverseMemory(void *const pv,size_t const quantity_bytes)
{
int const assert_dummy = (assert(!!pv),0);

char unsigned *p = pv,
*q = p + (quantity_bytes - 1);

for( ; q p; ++p, --q)
{
unsigned const temp = ByteReversal(*p);
*p = ByteReversal(*q);
*q = temp;
}
}

int main(void)
{
unsigned arr[64] = {0,1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63};

unsigned const *p, *const q = arr + sizeof arr/sizeof*arr;

p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");
}

--

Frederick Gotham

Your "ReverseMemory" function has a small BUG.
It cannot work rightly while the "quantity_bytes" parameter is a odd
number.
Here's my code, point out mistakes please:
#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

// Function-pointer for Reverse-functions
typedef Tchar (*ptrRevCharFun)(Tchar);

// Define Reverse-functions
Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need
///////////////////////////////////////////////

// To select a correct function by CHAR_BIT of this machine
// If you didn't define a function for this
// machine, you will get a compile-time error
#if CHAR_BIT == 8
ptrRevCharFun g_pFunRevChar = RevChar8;
#endif
#if CHAR_BIT == 16
ptrRevCharFun g_pFunRevChar = RevChar16; // if you need
#endif
#if CHAR_BIT == 32
ptrRevCharFun g_pFunRevChar = RevChar32; // if you need
#endif
///////////////////////////////////////////////

// Reverse-function for 8-bit char only
Tchar RevChar8 (Tchar value)
{
value = ((value & 0x0fu) << 4) | ((value & 0xf0u) >4);
value = ((value & 0x33u) << 2) | ((value & 0xccu) >2);
return ((value & 0x55u) << 1) | ((value & 0xaau) >1);
}

// Memory-Reverse
void RevMemory (Tchar *begin,
Tchar *end)
{
Tchar temp;
for (end--; begin <= end; ++begin, --end)
{
temp = g_pFunRevChar(*begin); // If you got a "identifier not found"
error here,
*begin = g_pFunRevChar(*end); // Maybe you need to define a new
Reverse-function
*end = temp; // for this new machine.
}
}

// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op = ' ')
{
Tchar mask = 1u << (CHAR_BIT - 1);
int i;
for (i = 0; i < CHAR_BIT; ++i)
{
if (value & mask) putchar('1'); else putchar('0');
value <<= 1;
}
putchar(op);
}

// For Debug and Test
void ShowBinMemory (Tchar *begin,
Tchar *end,
Tchar op = '\n')
{
while (begin != end)
ShowBinChar (*begin++);
putchar(op);
}

int main()
{
Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

ShowBinMemory (a, a + sizeof(a));

RevMemory (a, a + sizeof(a));

ShowBinMemory (a, a + sizeof(a));
}

[Aman JIANG]

Frederick Gotham wrote:

I was intrigued by someone the other day who posted regarding methods of
"mirror-imaging" the bits in a byte. I thought it might be interesting to
write a fully-portable algorithm for mirror-imaging (i.e. reversing) an
entire chunk of memory, and making the algorithm as fast as possible (yes,
I realise it may be faster on some machines than on others, but still, one
can aim for pretty high average efficiency across the board.)

Anyway, here's my latest code, feel free to tamper. I haven't gone through
it with a fine-tooth comb, so it might contain a bug or two. The method it
uses for reversing bits in a byte is based on the code that looked
something like:

| ((unsigned)val & 128) >7
| ((unsigned)val & 64) >6

Here it is:

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>

/* The following macro sets a specified
sole bit index. (It would be better
to perform the assertion using IMAX_BITS
rather than sizeof(unsigned)*CHAR_BIT).
*/

#define ISOLATE_BIT(index) (\
assert((index) < sizeof(unsigned)*CHAR_BIT), \
1U << (index) )

/* The next macro gives us the reversed bit index,
e.g. for 8-Bit bytes:

0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
*/

#define REVERSAL_BIT_POSITION(index) (\
assert((index) < CHAR_BIT), \
CHAR_BIT-1 - (index) )
char unsigned ByteReversal(char unsigned val)
{
unsigned index, reversal = 0;

/* Deal with shifting to the left first. */

for(index = 0; index != CHAR_BIT/2; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))
<< REVERSAL_BIT_POSITION(index) - index;
}

/* Now deal with shifting to the right. */

for(; index != CHAR_BIT; ++index)
{
reversal |= ((unsigned)val & ISOLATE_BIT(index))

>index - REVERSAL_BIT_POSITION(index);

}

return reversal;
}

void ReverseMemory(void *const pv,size_t const quantity_bytes)
{
int const assert_dummy = (assert(!!pv),0);

char unsigned *p = pv,
*q = p + (quantity_bytes - 1);

for( ; q p; ++p, --q)
{
unsigned const temp = ByteReversal(*p);
*p = ByteReversal(*q);
*q = temp;
}
}

int main(void)
{
unsigned arr[64] = {0,1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63};

unsigned const *p, *const q = arr + sizeof arr/sizeof*arr;

p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");
}

--

Frederick Gotham

Your "ReverseMemory" function has a small BUG.
It cannot work rightly while the "quantity_bytes" parameter is a odd
number.
Here's my code, point out mistakes please:
#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

// Function-pointer for Reverse-functions
typedef Tchar (*ptrRevCharFun)(Tchar);

// Define Reverse-functions
Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need
///////////////////////////////////////////////

// To select a correct function by CHAR_BIT of this machine
// If you didn't define a function for this
// machine, you will get a compile-time error
#if CHAR_BIT == 8
ptrRevCharFun g_pFunRevChar = RevChar8;
#endif
#if CHAR_BIT == 16
ptrRevCharFun g_pFunRevChar = RevChar16; // if you need
#endif
#if CHAR_BIT == 32
ptrRevCharFun g_pFunRevChar = RevChar32; // if you need
#endif
///////////////////////////////////////////////

// Reverse-function for 8-bit char only
Tchar RevChar8 (Tchar value)
{
value = ((value & 0x0fu) << 4) | ((value & 0xf0u) >4);
value = ((value & 0x33u) << 2) | ((value & 0xccu) >2);
return ((value & 0x55u) << 1) | ((value & 0xaau) >1);
}

// Memory-Reverse
void RevMemory (Tchar *begin,
Tchar *end)
{
Tchar temp;
for (end--; begin <= end; ++begin, --end)
{
temp = g_pFunRevChar(*begin);
*begin = g_pFunRevChar(*end);
*end = temp;
}
}

// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op = ' ')
{
Tchar mask = 1u << (CHAR_BIT - 1);
int i;
for (i = 0; i < CHAR_BIT; ++i)
{
if (value & mask) putchar('1'); else putchar('0');
value <<= 1;
}
putchar(op);
}

// For Debug and Test
void ShowBinMemory (Tchar *begin,
Tchar *end,
Tchar op = '\n')
{
while (begin != end)
ShowBinChar (*begin++);
putchar(op);
}

int main()
{
Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

ShowBinMemory (a, a + sizeof(a));

RevMemory (a, a + sizeof(a));

ShowBinMemory (a, a + sizeof(a));
}

[Frederick Gotham]

Could you please make sure that you only post each article once? You tend
to make multiple postings regularly.

Aman JIANG posted:

Your "ReverseMemory" function has a small BUG.

Please refrain from using ALL CAPS -- that is not how English is usually
written.

Simpy write "table" or "bug", not TABLE or BUG.

It cannot work rightly while the "quantity_bytes" parameter is a odd
number.

I'll have a look over the code when I get the chance.

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

The type of byte on _every_ machine is "unsigned char".

Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need
///////////////////////////////////////////////

You're forgetting:

9-Bit char's 21-Bit char's 32-Bit char's
11-Bit char's 22-Bit char's 33-Bit char's
12-Bit char's 23-Bit char's 34-Bit char's
13-Bit char's 24-Bit char's 35-Bit char's
14-Bit char's 25-Bit char's 36-Bit char's
15-Bit char's 26-Bit char's 37-Bit char's
16-Bit char's 27-Bit char's 38-Bit char's
17-Bit char's 28-Bit char's 39-Bit char's
18-Bit char's 29-Bit char's 40-Bit char's
19-Bit char's 30-Bit char's 41-Bit char's
20-Bit char's 31-Bit char's 42-Bit char's

All code posted to comp.lang.c should be fully portable, by which I mean it
should compile and run correctly on any conformaning implementation. The
code you posted is _not_ fully portable.

--

Frederick Gotham

[Matthew R. Dempsky]

On 2006-09-08, Frederick Gotham <fg*******@SPAM.comwrote:

You're forgetting:

{ N-bit char's : 9 <= N <= 42 }

All code posted to comp.lang.c should be fully portable, by which I mean it
should compile and run correctly on any conformaning implementation. The
code you posted is _not_ fully portable.

How's this?

unsigned char
rev_uchar (unsigned char c)
{
unsigned char x, v;

for (x = 0, v = ~0; v; v >>= 1, c >>= 1)
x = (x << 1) | (c & 1);

return x;
}

--
Posted via a free Usenet account from http://www.teranews.com

[Keith Thompson]

Frederick Gotham <fg*******@SPAM.comwrites:
[...]

You're forgetting:

9-Bit char's 21-Bit char's 32-Bit char's

[snip]

20-Bit char's 31-Bit char's 42-Bit char's

All code posted to comp.lang.c should be fully portable, by which I mean it
should compile and run correctly on any conformaning implementation. The
code you posted is _not_ fully portable.

I'd say it's acceptable to post non-portable code as long as you
acknowledge that it's non-portable.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[pete]

Matthew R. Dempsky wrote:

>
On 2006-09-08, Frederick Gotham <fg*******@SPAM.comwrote:

You're forgetting:

{ N-bit char's : 9 <= N <= 42 }

All code posted to comp.lang.c should be fully portable,
by which I mean it should compile and run correctly
on any conformaning implementation.
The code you posted is _not_ fully portable.

How's this?

unsigned char x, v;

v = ~0;

_not_ fully portable

unsigned char is allowed to have more value bits than type int.

v = -1; is fully portable
v = ~0u; is fully portable

--
pete

[Aman JIANG]

Frederick Gotham wrote:

Could you please make sure that you only post each article once? You tend
to make multiple postings regularly.

Sorry. Because my first post has a small format error.

Please refrain from using ALL CAPS -- that is not how English is usually
written.

Simpy write "table" or "bug", not TABLE or BUG.

I think it was proper noun, so i used capital letter.
Now I understand.

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

The type of byte on _every_ machine is "unsigned char".

Maybe.

Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need
///////////////////////////////////////////////

You're forgetting:

9-Bit char's 21-Bit char's 32-Bit char's
11-Bit char's 22-Bit char's 33-Bit char's

[snip]

19-Bit char's 30-Bit char's 41-Bit char's
20-Bit char's 31-Bit char's 42-Bit char's

All code posted to comp.lang.c should be fully portable, by which I mean it
should compile and run correctly on any conformaning implementation. The
code you posted is _not_ fully portable.

I think that I could never to see 9-Bit char, 33-Bit char or 42-Bit
char in my life.
Maybe I need a slow but general version of RevChar like RevCharAll,
and some fast and special version like RevChar8, RevChar16 and so on.

Is that perfect ?

[pete]

pete wrote:

>
Matthew R. Dempsky wrote:

On 2006-09-08, Frederick Gotham <fg*******@SPAM.comwrote:

You're forgetting:

{ N-bit char's : 9 <= N <= 42 }

All code posted to comp.lang.c should be fully portable,
by which I mean it should compile and run correctly
on any conformaning implementation.
The code you posted is _not_ fully portable.

How's this?

unsigned char x, v;

v = ~0;

_not_ fully portable

unsigned char is allowed to have more value bits than type int.

.... which doesn't even fully cover the portability problem.
In one's complement and signed magnitude representation,
(~0) is not equal to (-1)
and on implementations with those representations,
((unsigned char)~0) is not equal to UCHAR_MAX.

v = -1; is fully portable
v = ~0u; is fully portable

--
pete

[Aman JIANG]

Frederick Gotham wrote:

You're forgetting:

9-Bit char's 21-Bit char's 32-Bit char's
11-Bit char's 22-Bit char's 33-Bit char's
12-Bit char's 23-Bit char's 34-Bit char's
13-Bit char's 24-Bit char's 35-Bit char's
14-Bit char's 25-Bit char's 36-Bit char's
15-Bit char's 26-Bit char's 37-Bit char's
16-Bit char's 27-Bit char's 38-Bit char's
17-Bit char's 28-Bit char's 39-Bit char's
18-Bit char's 29-Bit char's 40-Bit char's
19-Bit char's 30-Bit char's 41-Bit char's
20-Bit char's 31-Bit char's 42-Bit char's

All code posted to comp.lang.c should be fully portable, by which I mean it
should compile and run correctly on any conformaning implementation. The
code you posted is _not_ fully portable.

This is my last version (Is this fully-portable now ?) :

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

// Function-pointer for Reverse-functions
typedef Tchar (*ptrRevCharFun)(Tchar);

// Define Reverse-functions
Tchar RevCharX (Tchar); // general version
Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need
///////////////////////////////////////////////

// To select a correct function by CHAR_BIT of this machine.
// If you didn't define a function for this
// machine, you'll get a general version.
ptrRevCharFun gToSelectReverseFunction(void)
{
ptrRevCharFun g_pFunRevChar = RevCharX; // general version
#if CHAR_BIT == 8
g_pFunRevChar = RevChar8; // special version for 8-bit char
#endif
#if CHAR_BIT == 16
g_pFunRevChar = RevChar16; // if you need
#endif
#if CHAR_BIT == 32
g_pFunRevChar = RevChar32; // if you need
#endif
return g_pFunRevChar;
}

ptrRevCharFun g_pFunRevChar = gToSelectReverseFunction();

///////////////////////////////////////////////
// Reverse-function for 8-bit char only
Tchar RevChar8 (Tchar value)
{
value = ((value & 0x0fu) << 4) | ((value & 0xf0u) >4);
value = ((value & 0x33u) << 2) | ((value & 0xccu) >2);
return ((value & 0x55u) << 1) | ((value & 0xaau) >1);
}

Tchar RevCharX (Tchar value)
{
Tchar ret = 0;
int i = 0, j = 0;
for(i = (CHAR_BIT - 1); i >= 0; --i)
{
ret += (((value << i) & (1u << (CHAR_BIT - 1))) >(j++));
}
return ret;
}

// Memory-Reverse
void RevMemory (Tchar *begin,
Tchar *end)
{
Tchar temp;
for (end--; begin <= end; ++begin, --end)
{
temp = g_pFunRevChar(*begin);
*begin = g_pFunRevChar(*end);
*end = temp;
}

}
// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op = ' ')
{
Tchar mask = 1u << (CHAR_BIT - 1);
int i;
for (i = 0; i < CHAR_BIT; ++i)
{
if (value & mask) putchar('1'); else putchar('0');
value <<= 1;
}
putchar(op);

}
// For Debug and Test
void ShowBinMemory (Tchar *begin,
Tchar *end,
Tchar op = '\n')
{
while (begin != end)
ShowBinChar (*begin++);
putchar(op);

}
int main()
{
Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

ShowBinMemory (a, a + sizeof(a));

RevMemory (a, a + sizeof(a));

ShowBinMemory (a, a + sizeof(a));
}

[Keith Thompson]

"Aman JIANG" <Am*******@gmail.comwrites:

Frederick Gotham wrote:

>Could you please make sure that you only post each article once? You tend
to make multiple postings regularly.

Sorry. Because my first post has a small format error.

Articles can be delivered in arbitrary order, and readers can't easily
tell which one was the original and which was the correction. We
can't even tell that one of them is a correction unless you tell us.

Once you post an article, it's out there (cancellations often don't
work). If you need to correct an error, post a followup.

>Please refrain from using ALL CAPS -- that is not how English is usually
written.

Simpy write "table" or "bug", not TABLE or BUG.

I think it was proper noun, so i used capital letter.
Now I understand.

Ok, but that's not what "proper nouns" are, and proper nouns aren't
written in ALL CAPS.

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;

The type of byte on _every_ machine is "unsigned char".

Maybe.

No, definitely. The word "byte" is defined that way by the C
standard. (A "byte" may or may not be 8 bits.)

[...]

I think that I could never to see 9-Bit char, 33-Bit char or 42-Bit
char in my life.

Perhaps, but most code shouldn't care how big characters are, or
should determine it by looking at CHAR_BIT. (Most, not all; sometimes
non-portable code is appropriate.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Peter Nilsson]

Frederick Gotham wrote:

I was intrigued by someone the other day who posted regarding methods of
"mirror-imaging" the bits in a byte. I thought it might be interesting to
write a fully-portable algorithm for mirror-imaging (i.e. reversing) an
entire chunk of memory, and making the algorithm as fast as possible (yes,
I realise it may be faster on some machines than on others, but still, one
can aim for pretty high average efficiency across the board.)

Or just use big-O on some measure, like say the number of 1 position
shifts.

/* mirror reverse memory range [p..q) */
void mirror_range(void *p, void *q)
{
unsigned char m, x, y, uc, *up, *uq;

for (up = p, uq = q; up < --uq; up++)
{ uc = *up; *up = *uq; *uq = uc; }

for (up = p, uq = q; up < uq; up++)
{
for (x = *up, m = -1; m; x >>= 1, m >>= 1)
y = (y << 1) | (x & 1);
*up = y;
}
}

[P.S. since this is about raw speed, I shaved a few femto-seconds by
dumping the initialisation of y. ;-]

Anyway, here's my latest code, feel free to tamper. I haven't gone through
it with a fine-tooth comb, so it might contain a bug or two.

<snip>

unsigned arr[64] = {0,1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63};

unsigned const *p, *const q = arr + sizeof arr/sizeof*arr;

p = arr;
do printf("%u ",*p++);
while (p!=q);
puts("");

ReverseMemory(arr,sizeof arr);
p = arr;
do printf("%u ",*p++);

Since you mention portability, you should know that you have no
guarantee
that your 'reversed' unsigned ints are not (now) trap representations.

--
Peter

[Richard Heathfield]

Aman JIANG said:

<snip>

This is my last version (Is this fully-portable now ?) :

On my system, it doesn't even preprocess, let alone compile:

foo.c:22: unterminated character constant
foo.c:23: unterminated character constant
make: *** [foo.o] Error 1

So I'd call that not just non-portable but actually broken.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Keith Thompson]

"Aman JIANG" <Am*******@gmail.comwrites:
[...]

This is my last version (Is this fully-portable now ?) :

No.

#include <assert.h>
#include <stddef.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

<memory.his not a standard header.

[snip]

ptrRevCharFun g_pFunRevChar = gToSelectReverseFunction();

The initializer for a static object must be constant.

[snip]

// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op = ' ')

The "= ' '" is a syntax error. (You can't specify default values for
parameters.)

[snip]

But I noticed that your code compiled without error as C++.

Try using a C compiler (or posting to comp.lang.c++).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Aman JIANG]

Richard Heathfield wrote:

Aman JIANG said:

<snip>

This is my last version (Is this fully-portable now ?) :

On my system, it doesn't even preprocess, let alone compile:

foo.c:22: unterminated character constant
foo.c:23: unterminated character constant
make: *** [foo.o] Error 1

So I'd call that not just non-portable but actually broken.

Keith Thompson wrote:

<memory.his not a standard header.

ptrRevCharFun g_pFunRevChar = gToSelectReverseFunction();

The initializer for a static object must be constant.

// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op = ' ')

The "= ' '" is a syntax error. (You can't specify default values for
parameters.)

But I noticed that your code compiled without error as C++.

Try using a C compiler (or posting to comp.lang.c++).

Sorry I am using a C++ compiler, and I have forgot some C syntaxes.

This is my last version, I tested on GNU C (is it fully-portable now? )

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits.h>

// Define the Type of Byte of this Machine
typedef unsigned char Tchar;
// Function-pointer for Reverse-functions
typedef Tchar (*ptrRevCharFun)(Tchar);

// Define Reverse-functions
Tchar RevCharX (Tchar); // general version
Tchar RevChar8 (Tchar); // for 8-bit char only
// Tchar RevChar16 (Tchar); // if you need
// Tchar RevChar32 (Tchar); // if you need

// A global pointer of Reverse-function for RevMemory
// Call Initialize to select a correct function for
// your machine.
ptrRevCharFun g_pFunRevChar = 0;

// To select a correct function by CHAR_BIT of this machine.
// If you didn't define a function for this
// machine, you'll get a general version.
void Initialize (void)
{
g_pFunRevChar = RevCharX;
if (CHAR_BIT == 8) {
g_pFunRevChar = RevChar8;
}
//else if {CHAR_BIT == 16} // if you need
//else if {CHAR_BIT == 32} // if you need
}
///////////////////////////////////////////////
// Reverse-function for 8-bit char only
Tchar RevChar8 (Tchar value)
{
value = ((value & 0x0fu) << 4) | ((value & 0xf0u) >4);
value = ((value & 0x33u) << 2) | ((value & 0xccu) >2);
return ((value & 0x55u) << 1) | ((value & 0xaau) >1);
}

Tchar RevCharX (Tchar value)
{
Tchar ret = 0;
int i = 0, j = 0;
for(i = (CHAR_BIT - 1); i >= 0; --i)
{
ret += (((value << i) & (1u << (CHAR_BIT - 1))) >(j++));
}
return ret;
}
// Memory-Reverse
void RevMemory (Tchar *begin,
Tchar *end)
{
Tchar temp;
for (end--; begin <= end; ++begin, --end)
{
temp = g_pFunRevChar(*begin);
*begin = g_pFunRevChar(*end);
*end = temp;
}
}
// For Debug and Test
void ShowBinChar (Tchar value,
Tchar op)
{
Tchar mask = 1u << (CHAR_BIT - 1);
int i;
for (i = 0; i < CHAR_BIT; ++i)
{
if (value & mask) putchar('1'); else putchar('0');
value <<= 1;
}
putchar(op);
}

// For Debug and Test
void ShowBinMemory (Tchar *begin,
Tchar *end,
Tchar op)
{
while (begin != end)
ShowBinChar (*begin++, ' ');
putchar(op);
}

int main()
{
Initialize();

Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

ShowBinMemory (a, a + sizeof(a), '\n');

RevMemory (a, a + sizeof(a));

ShowBinMemory (a, a + sizeof(a), '\n');
}

[Keith Thompson]

Richard Heathfield <in*****@invalid.invalidwrites:

Aman JIANG said:

<snip>

>This is my last version (Is this fully-portable now ?) :

On my system, it doesn't even preprocess, let alone compile:

foo.c:22: unterminated character constant
foo.c:23: unterminated character constant
make: *** [foo.o] Error 1

So I'd call that not just non-portable but actually broken.

The affected lines are:

// If you didn't define a function for this
// machine, you'll get a general version.

A C90 compiler that doesn't recognize "//" comments will treat the
"//" as two "/" delimiters (which will cause a syntax error if it
survives preprocessing). The rest of each line is a series of
identifiers (and a comma on the second line), but each apostrophe is
interpreted as introducing a character constant which is never
completed.

(IMHO it would make sense for a strict C90 compiler to recognize "//"
comments so it can issue clearer error messages. Note that two
adjacent '/' characters can appear in legal C90: a division operator
immediately followed by a "/*...*/" comment, or vice versa.)

But even with a compiler configured to accept "//" comments (which are
both non-portable and discouraged in this newsgroup, because they can
cause problems with line wrapping), there are numerous other problems
with the program, as I posted elsethread.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Richard Heathfield]

Aman JIANG said:

<snip>

>
This is my last version,

So was your previous version.

foo.c:23: unterminated character constant
foo.c:24: unterminated character constant
make: *** [foo.o] Error 1
Again, it fails to pre-process. But let's fix that, and see what happens.

I fixed this by removing any line, or part-line, beginning with //

This left me with the following diagnostic messages, the first five of which
it is perhaps forgiveable to ignore, but the parse error is a show-stopper:

foo.c:15: warning: no previous prototype for `Initialize'
foo.c:43: warning: no previous prototype for `RevMemory'
foo.c:56: warning: no previous prototype for `ShowBinChar'
foo.c:70: warning: no previous prototype for `ShowBinMemory'
foo.c:77: warning: function declaration isn't a prototype
foo.c: In function `main':
foo.c:80: parse error before `a'
foo.c:82: `a' undeclared (first use in this function)
foo.c:82: (Each undeclared identifier is reported only once
foo.c:82: for each function it appears in.)
foo.c:87: warning: control reaches end of non-void function
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Richard Heathfield]

Frederick Gotham said:

<snip>

All code posted to comp.lang.c should be fully portable, by which I mean
it should compile and run correctly on any conformaning implementation.

That isn't the case. Otherwise, since printf need not be provided by
freestanding implementations, it would be off-topic here!

K&R code is topical here.
Freestanding C90 code is topical here.
Hosted C90 code is topical here.
Freestanding C99 code is topical here.
Hosted C99 code is topical here.

If a program happens to fall into more than one of those categories, so much
the better.

The code you posted is _not_ fully portable.

Certainly true, and it is because he asked whether it was fully portable
that I made the comments I did about it. Nevertheless, it appears - at
first sight, at least - to be a valid C99 program.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Aman JIANG]

Richard Heathfield wrote:

This left me with the following diagnostic messages, the first five of which
it is perhaps forgiveable to ignore, but the parse error is a show-stopper:

foo.c:15: warning: no previous prototype for `Initialize'
foo.c:43: warning: no previous prototype for `RevMemory'
foo.c:56: warning: no previous prototype for `ShowBinChar'
foo.c:70: warning: no previous prototype for `ShowBinMemory'
foo.c:77: warning: function declaration isn't a prototype
foo.c: In function `main':
foo.c:80: parse error before `a'
foo.c:82: `a' undeclared (first use in this function)
foo.c:82: (Each undeclared identifier is reported only once
foo.c:82: for each function it appears in.)
foo.c:87: warning: control reaches end of non-void function

Oh my god.
I have not gotten any warning on gcc.
Could you please help me to fix the bugs, and show me
a perfect version on your system ?

[Richard Heathfield]

Aman JIANG said:

<snip>

I have not gotten any warning on gcc.

I used the following flags:

-W -Wall -ansi -pedantic -Wformat-nonliteral -Wcast-align -Wpointer-arith
-Wbad-function-cast -Wmissing-prototypes -Wstrict-prototypes
-Wmissing-declarations -Winline -Wundef -Wnested-externs -Wcast-qual
-Wshadow -Wconversion -Wwrite-strings -Wno-conversion -ffloat-store -O2

Could you please help me to fix the bugs,

They aren't necessarily bugs. I'm just pointing out that your code isn't
fully portable. That doesn't mean it's *wrong* - it just means I can't
compile it here, using a C90-conforming implementation.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Aman JIANG]

Richard Heathfield wrote:

Aman JIANG said:

<snip>

I have not gotten any warning on gcc.

I used the following flags:

-W -Wall -ansi -pedantic -Wformat-nonliteral -Wcast-align -Wpointer-arith
-Wbad-function-cast -Wmissing-prototypes -Wstrict-prototypes
-Wmissing-declarations -Winline -Wundef -Wnested-externs -Wcast-qual
-Wshadow -Wconversion -Wwrite-strings -Wno-conversion -ffloat-store -O2

Could you please help me to fix the bugs,

They aren't necessarily bugs. I'm just pointing out that your code isn't
fully portable. That doesn't mean it's *wrong* - it just means I can't
compile it here, using a C90-conforming implementation.

So, how to fix my code that make it could be full-portable, please ?
Or make it could accord with C90 ?

[Richard Heathfield]

Aman JIANG said:

Richard Heathfield wrote:

>Aman JIANG said:

<snip>

I have not gotten any warning on gcc.

I used the following flags:

-W -Wall -ansi -pedantic -Wformat-nonliteral -Wcast-align -Wpointer-arith
-Wbad-function-cast -Wmissing-prototypes -Wstrict-prototypes
-Wmissing-declarations -Winline -Wundef -Wnested-externs -Wcast-qual
-Wshadow -Wconversion -Wwrite-strings -Wno-conversion -ffloat-store -O2

Could you please help me to fix the bugs,

They aren't necessarily bugs. I'm just pointing out that your code isn't
fully portable. That doesn't mean it's *wrong* - it just means I can't
compile it here, using a C90-conforming implementation.

So, how to fix my code that make it could be full-portable, please ?
Or make it could accord with C90 ?

To make it C90-conforming, you could start off by using /* comments */
instead of // comments

Also, you could define objects at the beginning of a block, rather than mix
them up with code.

And you could return a value from main.

Consider:

int main(void)
{

Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

Initialize();
ShowBinMemory (a, a + sizeof(a), '\n');
RevMemory (a, a + sizeof(a));
ShowBinMemory (a, a + sizeof(a), '\n');

return 0;
}
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Aman JIANG]

Richard Heathfield wrote:

Aman JIANG said:

Richard Heathfield wrote:

Aman JIANG said:

<snip>

I have not gotten any warning on gcc.

I used the following flags:

-W -Wall -ansi -pedantic -Wformat-nonliteral -Wcast-align -Wpointer-arith
-Wbad-function-cast -Wmissing-prototypes -Wstrict-prototypes
-Wmissing-declarations -Winline -Wundef -Wnested-externs -Wcast-qual
-Wshadow -Wconversion -Wwrite-strings -Wno-conversion -ffloat-store -O2

Could you please help me to fix the bugs,

They aren't necessarily bugs. I'm just pointing out that your code isn't
fully portable. That doesn't mean it's *wrong* - it just means I can't
compile it here, using a C90-conforming implementation.

So, how to fix my code that make it could be full-portable, please ?
Or make it could accord with C90 ?

To make it C90-conforming, you could start off by using /* comments */
instead of // comments

Also, you could define objects at the beginning of a block, rather than mix
them up with code.

And you could return a value from main.

Consider:

int main(void)
{

Tchar a[] = {'a', 'b', 'c', 'd', 'e'};

Initialize();
ShowBinMemory (a, a + sizeof(a), '\n');
RevMemory (a, a + sizeof(a));
ShowBinMemory (a, a + sizeof(a), '\n');

return 0;
}

Oh. Thanks for your help. Now I get it.

[Frederick Gotham]

Peter Nilsson posted:

Since you mention portability, you should know that you have no
guarantee
that your 'reversed' unsigned ints are not (now) trap representations.

Yes, I realise that. The code in "main" is simply for testing the portable
function.

--

Frederick Gotham

[Peter Nilsson]

Frederick Gotham wrote:

Peter Nilsson posted:

Since you mention portability, you should know that you have no
guarantee that your 'reversed' unsigned ints are not (now) trap

representations.

Yes, I realise that.

Then why post it to comp.lang.c?

The code in "main" is simply for testing the portable function.

What makes you think that you can't do that with portable code?

Portable programming isn't a concept you use solely for theoretical
exercises and 'games', then cast aside when the 'real' programming
begins. ;-)

--
Peter

[Dave Thompson]

On Sat, 09 Sep 2006 10:41:39 +0000, Richard Heathfield
<in*****@invalid.invalidwrote:

Aman JIANG said:

<snip>

This is my last version,

So was your previous version.

<OTHe(?) may have used 'last' to mean 'most recent', 'latest'. I
have found this imprecise but I think not definitively wrong usage
common even in native English speakers, which he clearly is not.

<SemiOnTopicIn fact, I have found this so common I consciously avoid
using 'last' in either sense in code. When dealing with linked lists
and other linked/dynamic data structures, I use next and prev, and
head and tail, never last. And usually similarly for files.

<snip substantive comments>

- David.Thompson1 at worldnet.att.net