1 /* byte_order.c - byte order related platform dependent routines,
2 *
3 * Copyright: 2008 Aleksey Kravchenko <rhash.admin@gmail.com>
4 *
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so.
11 */
12
13 #include <unistd.h>
14 #include <stdlib.h> /* size_t for vc6.0 */
15 #include "byte_order.h"
16
17 #if !(__GNUC__ >= 4 || (__GNUC__ ==3 && __GNUC_MINOR__ >= 4)) /* if !GCC or GCC < 4.3 */
18
19 # if _MSC_VER >= 1300 && (_M_IX86 || _M_AMD64 || _M_IA64) /* if MSVC++ >= 2002 on x86/x64 */
20 # include <intrin.h>
21 # pragma intrinsic(_BitScanForward)
22
23 /**
24 * Returns index of the trailing bit of x.
25 *
26 * @param x the number to process
27 * @return zero-based index of the trailing bit
28 */
rhash_ctz(unsigned x)29 unsigned rhash_ctz(unsigned x)
30 {
31 unsigned long index;
32 unsigned char isNonzero = _BitScanForward(&index, x); /* MSVC intrinsic */
33 return (isNonzero ? (unsigned)index : 0);
34 }
35 # else /* _MSC_VER >= 1300... */
36
37 /**
38 * Returns index of the trailing bit of a 32-bit number.
39 * This is a plain C equivalent for GCC __builtin_ctz() bit scan.
40 *
41 * @param x the number to process
42 * @return zero-based index of the trailing bit
43 */
rhash_ctz(unsigned x)44 unsigned rhash_ctz(unsigned x)
45 {
46 /* array for conversion to bit position */
47 static unsigned char bit_pos[32] = {
48 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
49 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
50 };
51
52 /* The De Bruijn bit-scan was devised in 1997, according to Donald Knuth
53 * by Martin Lauter. The constant 0x077CB531UL is a De Bruijn sequence,
54 * which produces a unique pattern of bits into the high 5 bits for each
55 * possible bit position that it is multiplied against.
56 * See http://graphics.stanford.edu/~seander/bithacks.html
57 * and http://chessprogramming.wikispaces.com/BitScan */
58 return (unsigned)bit_pos[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
59 }
60 # endif /* _MSC_VER >= 1300... */
61 #endif /* !(GCC >= 4.3) */
62
63 /**
64 * Copy a memory block with simultaneous exchanging byte order.
65 * The byte order is changed from little-endian 32-bit integers
66 * to big-endian (or vice-versa).
67 *
68 * @param to the pointer where to copy memory block
69 * @param index the index to start writing from
70 * @param from the source block to copy
71 * @param length length of the memory block
72 */
rhash_u32_swap_copy(void * to,int index,const void * from,size_t length)73 void rhash_u32_swap_copy(void* to, int index, const void* from, size_t length)
74 {
75 /* if all pointers and length are 32-bits aligned */
76 if( 0 == (( (int)((char*)to - (char*)0) | ((char*)from - (char*)0) | index | length ) & 3) ) {
77 /* copy memory as 32-bit words */
78 const uint32_t* src = (const uint32_t*)from;
79 const uint32_t* end = (const uint32_t*)((const char*)src + length);
80 uint32_t* dst = (uint32_t*)((char*)to + index);
81 while(src < end) *(dst++) = bswap_32( *(src++) );
82 } else {
83 const char* src = (const char*)from;
84 for(length += index; (size_t)index < length; index++) ((char*)to)[index ^ 3] = *(src++);
85 }
86 }
87
88 /**
89 * Copy a memory block with simultaneous exchanging byte order.
90 * The byte order is changed from little-endian 64-bit integers
91 * to big-endian (or vice-versa).
92 *
93 * @param to the pointer where to copy memory block
94 * @param index the index to start writing from
95 * @param from the source block to copy
96 * @param length length of the memory block
97 */
rhash_u64_swap_copy(void * to,int index,const void * from,size_t length)98 void rhash_u64_swap_copy(void* to, int index, const void* from, size_t length)
99 {
100 /* if all pointers and length are 64-bits aligned */
101 if( 0 == (( (int)((char*)to - (char*)0) | ((char*)from - (char*)0) | index | length ) & 7) ) {
102 /* copy aligned memory block as 64-bit integers */
103 const uint64_t* src = (const uint64_t*)from;
104 const uint64_t* end = (const uint64_t*)((const char*)src + length);
105 uint64_t* dst = (uint64_t*)((char*)to + index);
106 while(src < end) *(dst++) = bswap_64( *(src++) );
107 } else {
108 const char* src = (const char*)from;
109 for(length += index; (size_t)index < length; index++) ((char*)to)[index ^ 7] = *(src++);
110 }
111 }
112
113 /**
114 * Exchange byte order in the given array of 32-bit integers.
115 *
116 * @param arr the array to process
117 * @param length array length
118 */
rhash_u32_memswap(unsigned * arr,int length)119 void rhash_u32_memswap(unsigned *arr, int length)
120 {
121 unsigned* end = arr + length;
122 for(; arr < end; arr++) {
123 *arr = bswap_32(*arr);
124 }
125 }
126