Author: Dann Corbit
Date: 21:59:23 04/09/02
Go up one level in this thread
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
typedef unsigned char uc;
typedef unsigned long uint32;
static char string[32767];
static char saved[32767];
uc *reverse_s0(uc * s)
{
size_t nbyte;
if ((nbyte = strlen(s))) {
uc *p = s + nbyte - 1;
uc *q = s;
uc c;
do {
c = *p;
*p = *q;
*q = c;
} while (!(p++ > --q));
}
return (s);
}
uc *reverse_s1(uc * s)
{
uc *last,
temp;
size_t lgh;
lgh = strlen(s);
last = s + lgh;
while (last-- > s) {
temp = *s;
*s++ = *last;
*last = temp;
} return s;
}
uc *reverse_s2(uc * s)
{
uint32 c,
i,
j;
for (i = 0, j = strlen(s) - 1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = (uc) c;
}
return s;
}
uc *reverse_s3(uc * s)
{
uc *last,
temp;
last = s + strlen(s); /* points to '\0' */
while (last-- > s) {
temp = *s;
*s++ = *last;
*last = temp;
}
return s;
}
uc *reverse_s4(uc * s)
{
uc *p1,
*p2;
if (!s || !*s)
return s;
for (p1 = s, p2 = s + strlen(s) - 1; p2 > p1; ++p1, --p2) {
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
} return s;
}
uc *reverse_s5(uc * s)
{
uc *beg = s;
uc *end = s;
uc c;
while (*s++) {;
}
s -= 2;
while (end < s) {
c = *end;
*end++ = *s;
*s-- = c;
} return (beg);
}
uc *reverse_s6(uc * s)
{
uc *beg,
*end,
c;
size_t length;
end = s + (length = strlen(beg = s)) - 1;
length >>= 1;
while (length--) {
c = *s;
*s++ = *end;
*end-- = c;
} return beg;
}
uint32 reverse_uint32a(uint32 x)
{
x = ((x & 0xAAAAAAAA) >> 1) | ((x & 0x55555555) << 1); /* swapping
pairs of 1
* bit */
x = ((x & 0xCCCCCCCC) >> 2) | ((x & 0x33333333) << 2); /* swapping
pairs of 2
* bits */
x = ((x & 0xF0F0F0F0) >> 4) | ((x & 0x0F0F0F0F) << 4); /* swapping
pairs of 4
* bits */
x = ((x & 0xFF00FF00) >> 8) | ((x & 0x00FF00FF) << 8); /* swapping
pairs of 8
* bits */
x = ((x & 0xFFFF0000) >> 16) | ((x & 0x0000FFFF) << 16); /* swapping
pairs of 16
* bits */
return x;
}
uint32 reverse_uint32b(uint32 v)
{
uint32 r = 0,
q = -1;
while (q) {
r = (r << 1) | (v & 1);
v >>= 1;
q >>= 1;
} return r;
}
uc reverse_chara(uc c)
{
uc hi = ~0; /* all bits 1 */
uc rev = c & 1;/* catch low bit of c */
hi ^= hi >> 1; /* just the high bit set */
c >>= 1;
c |= hi; /* high bit of c set, low bit lost */
while (c != 1) { /* while not reached sentinel value */
rev = rev << 1 | c & 1; /* roll in next bit (reversed) */
c >>= 1; /* and get rid of it */
}
return rev;
}
uc reverse_charb(uc b)
{
uc c;
c = (b & 0xf0) >> 4;
b = (b << 4); /* the & 0xf0 is normaly not needed */
b |= c;
c = (b & 0xcc) >> 2;
b = (b << 2) & 0xcc;
b |= c;
c = (b & 0xaa) >> 1;
b = (b << 1) & 0xaa;
b |= c;
return b;
}
uint32 reverse_uint32c(uint32 n)
{
unsigned r = 0,
j = 1,
m = n;
while (r = 2 * r + m % 2, j *= 2)
m /= 2;
return r;
}
uint32 reverse_uint32d(uint32 n)
{
unsigned r = 0,
j = 1;
while (r = r * 2 | n & 1, j *= 2)
n >>= 1;
return r;
}
uint32 reverse_uint32i(uint32 n)
{
return n ? reverse_uint32i(n << 1) << 1 : 0;
}
uc reverse_charc(uc b)
{
static unsigned short val;
static uc *p = (uc *) & val;
val = b << 5;
val = ((val & 0x0AA0) << 2) | (val & 0x1540);
val = ((val & 0x3300) >> 4) | (val & 0x0CC0);
return (p[0] | p[1]);
}
uc reverse_chard(uc b)
{
unsigned short val;
val = b << 5;
val = ((val & 0x0AA0) << 2) | (val & 0x1540);
val = ((val & 0x3300) >> 4) | (val & 0x0CC0);
b = val >> 8 | val & 0xf0;
return b;
}
uc reverse_chare(uc b)
{
uc m1 = 0xf0,
m2 = 0x0f,
r;
static uc T[] = {0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60,
0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0};
r = T[b & m2];
r = r | (T[(b & m1) >> 4] >> 4);
return r;
}
uc reverse_charf(uc b)
{
uc m1 = 0xf0,
m2 = 0x0f,
r;
static uc T[] = {0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60,
0xe0, 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0};
static uc S[] = {0x00, 0x08, 0x04, 0x0c, 0x02, 0x0a, 0x06,
0x0e, 0x01, 0x09, 0x05, 0x0d, 0x03, 0x0b, 0x07, 0x0f};
r = T[b & m2];
r = r | (S[(b & m1) >> 4]);
return r;
}
uc reverse_charg(uc b)
{
/* 76543210 */
b = b >> 4 | b << 4; /* 32107654 */
b = (b & 0xcc) >> 2 | (b & 0x33) << 2; /* 10325476 */
b = (b & 0xaa) >> 1 | (b & 0x55) << 1; /* 01234567 */
return b;
}
uc reverse_charh(uc b)
{
uint32 k;
uc m1 = 1 << 7,
m2 = 1,
r = 0;
for (k = 1; k <= 8; ++k) {
if (b & m2)
r |= m1;
m1 >>= 1;
m2 <<= 1;
}
return r;
}
static const uc ReversedBitTable[256] =
{
0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff
};
uc reverse_chari(uc b)
{
return ReversedBitTable[b];
}
uc reverse_charj(uc b)
{
uc r = 0,
i;
for (i = 8; i--; b >>= 1)
r = (r << 1) | (b & 1);
return r;
}
uc reverse_chark(uc b)
{ /* BROKEN */
uc c;
c = ((b >> 1) & 0x55) | ((b << 1) & 0xaa);
c |= ((b >> 2) & 0x33) | ((b << 2) & 0xcc);
c |= ((b >> 4) & 0x0f) | ((b << 4) & 0xf0);
return c;
}
uc reverse_charl(uc a)
{
return ((a & 0x80) >> 7)
| ((a & 0x40) >> 5)
| ((a & 0x20) >> 3)
| ((a & 0x10) >> 1)
| ((a & 0x08) << 1)
| ((a & 0x04) << 3)
| ((a & 0x02) << 5)
| ((a & 0x01) << 7);
}
unsigned int revword[65536];
void init_reverse_uint32j(void)
{
unsigned long i;
for (i = 0; i <= 65535; i++) {
unsigned long q = i;
unsigned char *p = (unsigned char *) &q;
unsigned char c = reverse_chari(p[1]);
p[1] = reverse_chari(p[0]);
p[0] = c;
revword[i] = q;
}
}
uint32 reverse_uint32j(uint32 n)
{
unsigned long l;
unsigned short *p = (unsigned short *) &n;
unsigned short *q = (unsigned short *) &l;
q[0] = revword[p[1]];
q[1] = revword[p[0]];
return l;
}
uint32 reverse_uint32k(uint32 n)
{
unsigned long l;
unsigned char *p = (unsigned char *) &n;
unsigned char *q = (unsigned char *) &l;
q[0] = ReversedBitTable[p[3]];
q[1] = ReversedBitTable[p[2]];
q[2] = ReversedBitTable[p[1]];
q[3] = ReversedBitTable[p[0]];
return l;
}
typedef uc *(*sf) (uc *);
#ifdef TEST_FROM_FILE
void bench_string_reverser(sf revstr)
{
uc s[8192];
FILE *fin = fopen("test.txt", "r");
if (fin) {
struct tm *newtime;
time_t aclock;
int i;
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
rewind(fin);
for (i = 0; i < 100; i++) {
rewind(fin);
while (fgets(s, sizeof s, fin)) {
revstr(s);
}
}
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
fclose(fin);
} else {
puts("Cannot open test.txt.");
exit(EXIT_FAILURE);
}
}
typedef uc(*ucf) (uc);
void bench_char_reverser(ucf revchr)
{
uc s[8192];
FILE *fin = fopen("test.txt", "r");
if (fin) {
struct tm *newtime;
time_t aclock;
int index = 0;
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
while (fgets(s, sizeof s, fin)) {
index = 0;
while (s[index]) {
revchr(s[index]);
index++;
}
}
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
fclose(fin);
} else {
puts("Cannot open test.txt.");
exit(EXIT_FAILURE);
}
}
#else
void bench_string_reverser(sf revstr)
{
struct tm *newtime;
time_t aclock;
int i;
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
for (i = 0; i < 10000; i++) {
revstr(string);
revstr(string);
if (strcmp(string, saved)) {
puts("broken...");
}
}
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
}
typedef uc(*ucf) (uc);
void bench_char_reverser(ucf revchr)
{
struct tm *newtime;
time_t aclock;
int i;
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
for (i = 0; i < 1000; i++) {
int index = 0;
unsigned char *s = string;
while (s[index]) {
int c = s[index];
c = revchr(c);
c = revchr(c);
if (c != s[index]) {
puts("broken...");
}
index++;
}
}
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
}
#endif
typedef uint32(*uif) (uint32);
void bench_uint32_reverser(uif revint)
{
struct tm *newtime;
time_t aclock;
int i;
unsigned long r;
unsigned long q;
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
for (i = 0; i < 10000000; ++i) {
q = r = rand();
q = revint(q);
q = revint(q);
if (q != r) {
puts("broken...");
}
}
time(&aclock);
newtime = localtime(&aclock);
puts(asctime(newtime));
}
typedef struct {
sf f;
char *s;
} sff;
typedef struct {
ucf f;
char *s;
} ucff;
typedef struct {
uif f;
char *s;
} uiff;
sff slist[] =
{
{
reverse_s0, "reverse_s0"
},
{
reverse_s1, "reverse_s1"
},
{
reverse_s2, "reverse_s2"
},
{
reverse_s3, "reverse_s3"
},
{
reverse_s4, "reverse_s4"
},
{
reverse_s5, "reverse_s5"
},
{
reverse_s6, "reverse_s6"
},
{
0, 0
}
};
ucff clist[] =
{
{
reverse_chara, "reverse_chara"
},
{
reverse_charb, "reverse_charb"
},
{
reverse_charc, "reverse_charc"
},
{
reverse_chard, "reverse_chard"
},
{
reverse_chare, "reverse_chare"
},
{
reverse_charf, "reverse_charf"
},
{
reverse_charg, "reverse_charg"
},
{
reverse_charh, "reverse_charh"
},
{
reverse_chari, "reverse_chari"
},
{
reverse_charj, "reverse_charj"
},
{
reverse_charl, "reverse_charl"
},
{
0, 0
}
};
uiff ilist[] =
{
{
reverse_uint32a, "reverse_uint32a"
},
{
reverse_uint32j, "reverse_uint32j"
},
{
reverse_uint32k, "reverse_uint32k"
},
{
0, 0
}
};
void init_string(void)
{
int i;
for (i = 0; i < 32765; i++)
string[i] = 'A' + i % 100;
strcpy(saved, string);
}
int main(void)
{
uint32 i;
init_reverse_uint32j();
init_string();
for (i = 0; slist[i].s; i++) {
puts(slist[i].s);
bench_string_reverser(slist[i].f);
}
for (i = 0; clist[i].s; i++) {
puts(clist[i].s);
bench_char_reverser(clist[i].f);
}
for (i = 0; ilist[i].s; i++) {
puts(ilist[i].s);
bench_uint32_reverser(ilist[i].f);
}
return 0;
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.