记忆逆转游戏 [英] Memory-reversal Game
问题描述
前几天我被某人发布了关于
" mirror-imaging"的方法的好奇心。一个字节中的位。我认为可能有趣的是
编写一个完全可移植的算法，用于镜像（即反转）一整块内存，并使算法尽可能快可能（是的，
我意识到它在某些机器上可能比在其他机器上更快，但仍然，一个
可以瞄准全面的高平均效率。）
无论如何，这是我的最新代码，随意篡改。我没有经过用细齿梳梳理它的b $ b，所以它可能包含一两个bug。它用于反转一个字节中的位的方法是基于看起来像
的代码：
| （（unsigned）val& 128）> 7
| （（unsigned）val& 64）> 6
这是：
#include< assert.h>
#include< stddef.h>
#include< limits.h>
#include< stdio.h>
/ *以下宏设置指定的
唯一位索引。 （使用IMAX_BITS来执行断言会更好
而不是sizeof（无符号）* CHAR_BIT）。
* /
#define ISOLATE_BIT（索引）（\
断言（（索引）< sizeof（unsigned）* CHAR_BIT），\
1U<<（index））
/ *下一个宏给出了反转位索引，
例如对于8位字节：
0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
* /
#define REVERSAL_BIT_POSITION（index）（\
断言（（索引）< CHAR_BIT），\
CHAR_BIT-1 - （索引））
char unsigned ByteReversal（char unsigned val）
{
无符号索引，反转= 0;
/ *先处理向左移动。 * /
for（index = 0; index！= CHAR_BIT / 2; ++ index）
{
reversal | =（（unsigned）val& ISOLATE_BIT（index））
<< REVERSAL_BIT_POSITION（index） - index;
}
/ *现在处理向右移动。 * /
for（; index！= CHAR_BIT; ++ index）
{
reversal | =（（unsigned） val& ISOLATE_BIT（index））
> index - REVERSAL_BIT_POSITION（index）;
}
退货逆转;
}
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（; qp; ++ 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）;
put（""）;
ReverseMemory（arr，sizeof arr）;
p = arr;
do printf（"％u，* p ++）;
while（p！= q）;
puts（""）;
}
-
Frederick Gotham
Frederick Gotham写道：
前几天我被某人发布了关于
" mirror-imaging" ;一个字节中的位。我认为可能有趣的是
编写一个完全可移植的算法，用于镜像（即反转）一整块内存，并使算法尽可能快可能（是的，
我意识到它在某些机器上可能比在其他机器上更快，但仍然，一个
可以瞄准全面的高平均效率。）
无论如何，这是我的最新代码，随意篡改。我没有经过用细齿梳梳理它的b $ b，所以它可能包含一两个bug。它用于反转一个字节中的位的方法是基于看起来像
的代码：
| （（unsigned）val& 128）> 7
| （（unsigned）val& 64）> 6
这是：
#include< assert.h>
#include< stddef.h>
#include< limits.h>
#include< stdio.h>
/ *以下宏设置指定的
唯一位索引。 （使用IMAX_BITS来执行断言会更好
而不是sizeof（无符号）* CHAR_BIT）。
* /
#define ISOLATE_BIT（索引）（\
断言（（索引）< sizeof（unsigned）* CHAR_BIT），\
1U<<（index））
/ *下一个宏给出了反转位索引，
例如对于8位字节：
0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
* /
#define REVERSAL_BIT_POSITION（index）（\
断言（（索引）< CHAR_BIT），\
CHAR_BIT-1 - （索引））
char unsigned ByteReversal（char unsigned val）
{
无符号索引，反转= 0;
/ *首先向左移动。 * /
for（index = 0; index！= CHAR_BIT / 2; ++ index）
{
reversal | =（（unsigned）val& ISOLATE_BIT（index））
<< REVERSAL_BIT_POSITION（index） - index;
}
/ *现在处理向右移动。 * /
for（; index！= CHAR_BIT; ++ index）
{
reversal | =（（unsigned） val& ISOLATE_BIT（index））
> index - REVERSAL_BIT_POSITION（index）;
}
退货逆转;
}
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（; qp; ++ 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,5 9，
60,61,62,63};
无符号const * p，* const q = arr + sizeof arr / sizeof * arr; < br $>
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
你的ReverseMemory函数有一个小BUG。
当quantity_bytes时，它无法正常工作。参数是一个奇怪的
数。
这是我的代码，请指出错误：
#include< assert.h>
#include< stddef.h>
#include< limits.h>
#include< stdio.h>
#include< stdlib.h>
#include< memory.h>
//定义字节类型这台机器
typedef unsigned char Tchar;
//反向函数的函数指针
typedef Tchar（* ptrRevCharFun） （Tchar）;
//定义反向函数
Tchar RevChar8（Tchar）; //仅适用于8位字符
// Tchar RevChar16（Tchar）; //如果你需要
// Tchar RevChar32（Tchar）; //如果你需要
///////////////////////////////////// //////////
//通过本机的CHAR_BIT选择正确的功能
//如果你没有为这个
//机器定义一个函数，你将得到一个编译时错误
#if CHAR_BIT == 8
ptrRevCharFun g_pFunRevChar = RevChar8;
#endif
#if CHAR_BIT == 16
ptrRevCharFun g_pFunRevChar = RevChar16; //如果你需要
#endif
#if CHAR_BIT == 32
ptrRevCharFun g_pFunRevChar = RevChar32; //如果你需要
#endif
/////////////////////////// ////////////////////
//仅限8位字符的反向函数
Tchar RevChar8（Tchar值）
{
value =（（值& 0x0fu）<< 4）| （（值& 0xf0u）> 4）;
value =（（值& 0x33u）<< 2）| （（值& 0xccu）> 2）;
return（（值& 0x55u）<< 1）| （（值& 0xaau）> 1）;
}
//内存反转
void RevMemory（Tchar *开始，
Tchar *结束）
{
Tchar temp;
for（end--; begin < = end; ++ begin， - end）
{
temp = g_pFunRevChar（* begin）; //如果你在这里找到了未找到标识符
错误，
* begin = g_pFunRevChar（* end）; //也许你需要定义一个新的
反转函数
* end = temp; //这个新机器。
}
}
//用于调试和测试
void ShowBinChar（Tchar值，
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）;
}
//用于调试和测试
void ShowBinMemory（Tchar * begin，
Tchar *结束，
Tchar op =''\ n''）
{
while（begin！= end）
ShowBinChar（*开始++）;
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写道：
前几天我被某人发布了关于
方法的人的好奇心"镜面成像"一个字节中的位。我认为可能有趣的是
编写一个完全可移植的算法，用于镜像（即反转）一整块内存，并使算法尽可能快可能（是的，
我意识到它在某些机器上可能比在其他机器上更快，但仍然，一个
可以瞄准全面的高平均效率。）
无论如何，这是我的最新代码，随意篡改。我没有经过用细齿梳梳理它的b $ b，所以它可能包含一两个bug。它用于反转一个字节中的位的方法是基于看起来像
的代码：
| （（unsigned）val& 128）> 7
| （（unsigned）val& 64）> 6
这是：
#include< assert.h>
#include< stddef.h>
#include< limits.h>
#include< stdio.h>
/ *以下宏设置指定的
唯一位索引。 （使用IMAX_BITS来执行断言会更好
而不是sizeof（无符号）* CHAR_BIT）。
* /
#define ISOLATE_BIT（索引）（\
断言（（索引）< sizeof（unsigned）* CHAR_BIT），\
1U<<（index））
/ *下一个宏给出了反转位索引，
例如对于8位字节：
0 - 7 4 - 3
1 - 6 5 - 2
2 - 5 6 - 1
3 - 4 7 - 0
* /
#define REVERSAL_BIT_POSITION（index）（\
断言（（索引）< CHAR_BIT），\
CHAR_BIT-1 - （索引））
char unsigned ByteReversal（char unsigned val）
{
无符号索引，反转= 0;
/ *首先向左移动。 * /
for（index = 0; index！= CHAR_BIT / 2; ++ index）
{
reversal | =（（unsigned）val& ISOLATE_BIT（index））
<< REVERSAL_BIT_POSITION（index） - index;
}
/ *现在处理向右移动。 * /
for（; index！= CHAR_BIT; ++ index）
{
reversal | =（（unsigned） val& ISOLATE_BIT（index））
> index - REVERSAL_BIT_POSITION（index）;
}
退货逆转;
}
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（; qp; ++ 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,5 9，
60,61,62,63};
无符号const * p，* const q = arr + sizeof arr / sizeof * arr; < br $>
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
你的ReverseMemory函数有一个小BUG。
当quantity_bytes时，它无法正常工作。参数是一个奇怪的
数。
这是我的代码，请指出错误：
#include< assert.h>
#include< stddef.h>
#include< limits.h>
#include< stdio.h>
#include< stdlib.h>
#include< memory.h>
//定义字节类型这台机器
typedef unsigned char Tchar;
//反向函数的函数指针
typedef Tchar（* ptrRevCharFun） （Tchar）;
//定义反向函数
Tchar RevChar8（Tchar）; //仅适用于8位字符
// Tchar RevChar16（Tchar）; //如果你需要
// Tchar RevChar32（Tchar）; //如果你需要
///////////////////////////////////// //////////
//通过本机的CHAR_BIT选择正确的功能
//如果你没有为这个
//机器定义一个函数，你将得到一个编译时错误
#if CHAR_BIT == 8
ptrRevCharFun g_pFunRevChar = RevChar8;
#endif
#if CHAR_BIT == 16
ptrRevCharFun g_pFunRevChar = RevChar16; //如果你需要
#endif
#if CHAR_BIT == 32
ptrRevCharFun g_pFunRevChar = RevChar32; //如果你需要
#endif
/////////////////////////// ////////////////////
//仅限8位字符的反向函数
Tchar RevChar8（Tchar值）
{
value =（（值& 0x0fu）<< 4）| （（值& 0xf0u）> 4）;
value =（（值& 0x33u）<< 2）| （（值& 0xccu）> 2）;
return（（值& 0x55u）<< 1）| （（值& 0xaau）> 1）;
}
//内存反转
void RevMemory（Tchar *开始，
Tchar *结束）
{
Tchar temp;
for（end--; begin < = end; ++ begin， - end）
{
temp = g_pFunRevChar（* begin）;
* begin = g_pFunRevChar （*结束）;
* end = temp;
}
}
//用于调试和测试
void ShowBinChar（Tchar值，
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）;
}
//用于调试和测试
void ShowBinMemory（Tchar * begin，
Tchar *结束，
Tchar op =''\ n''）
{
while（begin！= end）
ShowBinChar（*开始++）;
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发布：
你的 ; ReverseMemory"功能有一个小BUG。
请不要使用全部大写 - 这不是英语通常写的
。
Simpy写表或bug，而不是TABLE或BUG。
当quantity_bytes时，它无法正常工作。参数是奇数
数。
我有机会查看代码。
//定义本机的字节类型
typedef unsigned char Tchar;
_every_ machine上的字节类型是unsigned char。
Tchar RevChar8（Tchar）; //仅适用于8位字符
// Tchar RevChar16（Tchar）; //如果你需要
// Tchar RevChar32（Tchar）; //如果你需要
///////////////////////////////////// //////////
你忘记了：
9-bit char'' s 21-bit char'的32位字符'
11-bit char'的22-bit char'的33位字符'
12-bit char'的23-bit char'的34位字符'
13-bit char'的24-bit char'的35-bit char' 's
14-bit char'的25-bit char'的36-bit char''
15-bit char'的26-bit char '的37位字符'
16位字符'的27位字符'的38位字符'
17位char'的28-bit char'的39-bit char''
18-bit char'的29-bit char'的40-bit char''s&br / >
19-bit char'的30-bit char'的41位字符'
20-bit char'的31-bit char'的42- Bit char's
所有代码都发布到comp.lang.c sh应该是完全可移植的，我的意思是
应该在任何conformaning实现上编译和运行正确。您发布的
代码__完全便携。
-
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
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));
}
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));
}
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
这篇关于记忆逆转游戏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
