source: source/ariba/utility/serialization/DataUtilities.hpp@ 9633

Last change on this file since 9633 was 4622, checked in by mies, 15 years ago

fixed bug in arm shift operations due to compiler optimizations (hopefully!)
File size: 10.9 KB
Line 
1// [License]
2// The Ariba-Underlay Copyright
3//
4// Copyright (c) 2008-2009, Institute of Telematics, UniversitÀt Karlsruhe (TH)
5//
6// Institute of Telematics
7// UniversitÀt Karlsruhe (TH)
8// Zirkel 2, 76128 Karlsruhe
9// Germany
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17// 2. Redistributions in binary form must reproduce the above copyright
18// notice, this list of conditions and the following disclaimer in the
19// documentation and/or other materials provided with the distribution.
20//
21// THIS SOFTWARE IS PROVIDED BY THE INSTITUTE OF TELEMATICS ``AS IS'' AND
22// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
24// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE ARIBA PROJECT OR
25// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32//
33// The views and conclusions contained in the software and documentation
34// are those of the authors and should not be interpreted as representing
35// official policies, either expressed or implied, of the Institute of
36// Telematics.
37// [License]
38
39/* This file implements some common bit operations for unsigned integer types
40 * and arrays. There are two different approaches in indexing bits inside arrays
41 * and integrals:
42 *
43 * In simple integer types the least significant bit (LSB) is identified by index zero.
44 * A length is specified from the LSB to the MSB. On the other hand, there is an
45 * inverted form of this representation. In this case, the MSB is identfied by index
46 * zero and the length identifies a range from the MSB to the LSB.
47 *
48 * Normal Inverted
49 * MSB LSB MSB LSB
50 * v v v v
51 * +----------------+ +----------------+
52 * | uint16_t | | uint16_t |
53 * +----------------+ +----------------+
54 * ^ ^ ^ ^
55 * Index 15 0 0 15
56 * Length |<------+ +----->|
57 *
58 * Inside arrays the inverted form is used. Therefore an index of zero identifies the
59 * MSB of the first word in the array.
60 *
61 * TODO: TBC
62 */
63#ifndef DATAUTILITIES_HPP_
64#define DATAUTILITIES_HPP_
65
66#include "../internal/Utilities.hpp"
67
68#include <boost/cstdint.hpp>
69
70#include <memory>
71#include <string>
72
73template<typename X> finline
74static X shr( const X& value, unsigned int bits ) {
75 return (sizeof(X)*8 == bits) ? 0 : (value >> bits);
76}
77
78template<typename X> finline
79static X shl( const X& value, unsigned int bits ) {
80 return (sizeof(X)*8 == bits) ? 0 : (value << bits);
81}
82
83/**
84 * TODO: Doc
85 */
86template<typename X> finline
87static X bitblk(size_t index, size_t length, bool value, if_uint(X)) {
88 if (index == 0 && length >= sizeof(X) * 8) return value ? ~0 : 0;
89 X x = shl(( shl( ((X) 1), length) - 1), index);
90 return value ? x : ~x;
91}
92
93/**
94 * TODO: Doc
95 */
96template<typename X, bool value> finline
97static X bitblk(size_t index, size_t length, if_uint(X)) {
98 return bitblk<X> (index, length, value);
99}
100
101/**
102 * TODO: Doc
103 */
104template<typename X, bool value> finline
105static X bitblk(size_t length, if_uint(X)) {
106 if (length >= sizeof(X) * 8) return value ? ~0 : 0;
107 return value ? (((X) 1 << length) - 1) : ~(((X) 1 << length) - 1);
108}
109
110/**
111 * This method copies bits from one integral to another
112 */
113template<typename X, typename Y> finline
114static Y bitcpy(X src, size_t srcIdx, Y dst, size_t dstIdx, size_t len =
115 sizeof(X) * 8, bool srcInvert = false, bool dstInvert = false,
116 if_uint(X),if_uint (Y) ) {
117 if (srcInvert) srcIdx = sizeof(X) * 8 - srcIdx - len;
118 if (dstInvert) dstIdx = sizeof(Y) * 8 - dstIdx - len;
119 Y value = ((Y)shr(src, srcIdx)) << dstIdx;
120 Y mask = bitblk<Y, 0> (dstIdx, len);
121 return (dst & mask) | (value & ~mask);
122}
123
124/**
125 * This method copies bits from an array to another of the same
126 * integral type.
127 */
128template<typename X> finline
129static void bitcpy(X* src, size_t srcIdx, X* dst, size_t dstIdx, size_t len) {
130
131 // word width
132 const size_t w = sizeof(X) * 8;
133
134 // calculate indexes
135 size_t dwp = dstIdx % w, swp = srcIdx % w;
136 size_t idwp = w - dwp, iswp = w - swp;
137 dst += dstIdx / w;
138 src += srcIdx / w;
139
140 // check direct copy
141 if (dwp == 0 && swp == 0 && len % w == 0) {
142 memcpy(dst, src, len / 8);
143 return;
144 }
145
146 // check if first word only is affected
147 if ((dwp + len) <= w) {
148 X fw = shl(src[0],swp) | shr(src[1],iswp);
149 *dst = bitcpy(fw, 0, *dst, dwp, len, true, true);
150 return;
151 }
152
153 // set first word
154 if (idwp != 0) {
155 X fw = shl(src[0],swp) | shr(src[1],iswp);
156 *dst = (*dst & ~(((X) 1 << idwp) - 1)) | shr(fw,dwp);
157
158 // recalculate indexes & lengths
159 dst++;
160 src++;
161 len -= idwp;
162 swp = (swp + idwp) % w;
163 iswp = w - swp;
164 }
165
166 X a, b;
167
168 // copy whole words
169 if (swp == 0) {
170 size_t numWords = len / w;
171 // use memory copy
172 memcpy(dst, src, numWords * sizeof(X));
173 src += numWords;
174 dst += numWords;
175 len = len % w;
176 a = src[0], b = src[1];
177 } else {
178 // use shifted copy
179 a = src[0], b = src[1];
180 while (len >= w) {
181 *dst = shl(a,swp) | shr(b,iswp);
182 dst++;
183 src++;
184 len -= w;
185 a = b;
186 b = *src;
187 }
188 }
189
190 // set last word
191 X lw = shl(a,swp) | shr(b,iswp), lm = (shl((X) 1,(w - len)) - 1);
192 *dst = (*dst & lm) | (lw & ~lm);
193}
194
195
196
197/**
198 * array -> integral
199 */
200template<typename X, typename Y> finline
201static void bitcpy(X* src, size_t srcIdx, Y& dst, size_t dstIdx, size_t len =
202 sizeof(Y) * 8, if_uint(Y),if_uint (X) ) {
203
204 // word width
205 const size_t w = sizeof(X) * 8;
206
207 // calculate indexes
208 size_t swp = srcIdx % w, iswp = w - swp;
209 src += srcIdx / w;
210
211 // mask off bits
212 dst &= bitblk<Y,0>(dstIdx,len);
213
214 // copy whole words
215 X a = src[0], b = src[1];
216 Y value = 0;
217 src++;
218 while (len >= w) {
219 X x = shl(a,swp) | shr(b,iswp);
220 value <<= w;
221 value |= x;
222 src++;
223 len -= w;
224 a = b; b = *src;
225 }
226
227 // copy leftover
228 if ( len> 0 ) {
229 value <<= len;
230 value |= ((shl(a,swp) | shr(b,iswp)) >> (w - len)) & (shl(1,len)-1);
231 }
232
233 // set value
234 dst |= (value << dstIdx);
235 }
236
237/**
238 * TODO: Doc
239 */
240// word -> array
241template<typename X> finline
242static void bitcpy(X src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =
243 sizeof(X) * 8, bool srcInvert = false, if_uint(X)) {
244
245 // check inversion
246 if (srcInvert) srcIdx = sizeof(X) * 8 - srcIdx - len;
247
248 // word width
249 const size_t w = sizeof(X) * 8;
250
251 // calculate indexes
252 size_t dwp = dstIdx % w;
253 dst += dstIdx / w;
254
255 // copy directly
256 if (dwp == 0 && srcIdx == 0 && len == w) {
257 *dst = src;
258 } else
259
260 // copy non-overlapping word
261 if ((dwp + len) <= w) {
262 *dst = bitcpy(src, srcIdx, *dst, dwp, len, false, true);
263
264 // copy overlapping word
265 } else {
266 size_t idwp = w - dwp;
267 src >>= srcIdx;
268 X mask1 = ~(shl(1,idwp) - 1);
269 dst[0] = (dst[0] & mask1) | (shr(src,(len - idwp)) & ~mask1);
270 X mask2 = shl(1,(w - len + idwp)) - 1;
271 dst[1] = (dst[1] & mask2) | (shl(src, (w - len + idwp)) & ~mask2);
272 }
273}
274
275/**
276 * TODO: Doc
277 */
278// integral -> array
279template<typename Y, typename X> finline
280static void bitcpy(Y src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =
281 sizeof(Y) * 8, bool srcInvert = false, if_uint(X),if_uint (Y) ) {
282
283 if (sizeof(Y) <= sizeof(X)) {
284 // check inversion
285 if (srcInvert)
286 srcIdx = sizeof(Y) * 8 - srcIdx - len + (sizeof(X)-sizeof(Y))*8;
287 bitcpy((X)src,srcIdx,dst,dstIdx,len,false);
288 } else {
289 // check inversion
290 if (srcInvert) srcIdx = sizeof(Y) * 8 - srcIdx - len;
291 src = shr(src, srcIdx);
292
293 const size_t dw = sizeof(X)*8;
294 while (len >= dw) {
295 X word = (X)shr(src,(len-dw));
296 bitcpy(word,0,dst,dstIdx,dw);
297 dstIdx += dw;
298 len -= dw;
299 }
300 X word = (X)src;
301 bitcpy(word,0,dst,dstIdx,len);
302 }
303}
304
305/**
306 * TODO: Doc
307 */
308template<typename T, typename X> finline
309static T bitget(X* src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {
310 T x = 0;
311 bitcpy(src, idx, x, 0, len );
312 return x;
313}
314
315/**
316 * TODO: Doc
317 */
318template<typename T, typename X> finline
319static T bitget(X src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {
320 T x = 0;
321 bitcpy(src, idx, x, 0, len );
322 return x;
323}
324
325/**
326 * TODO: Doc
327 */
328template<typename X> finline
329static bool bitget(X* src, size_t index, if_uint(X)) {
330 uint8_t x = 0;
331 bitcpy(src, index, x, 0, 1);
332 return x != 0;
333}
334
335/**
336 * TODO: Doc
337 */
338template<typename X> finline
339static bool bitget(X src, size_t index, if_uint(X)) {
340 uint8_t x = 0;
341 x = bitcpy(src, index, x, 0, 1);
342 return x != 0;
343}
344
345/**
346 * TODO: Doc
347 */
348template<typename T, typename X> finline
349static void bitset(T src, X* dst, size_t index, if_uint(X),if_uint (T) ) {
350 bitcpy(src,0,dst,index);
351}
352
353/**
354 * TODO: Doc
355 */
356template<typename X> finline
357static void bitset(bool src, X* dst, size_t index, if_uint(X) ) {
358 bitcpy(src != 0, 0, dst, index, 1);
359}
360
361/**
362 * TODO: Doc
363 */
364template<typename X> finline
365static X bitset(bool src, X dst, size_t index, if_uint(X)) {
366 return bitcpy(src != 0, 0, dst, index, 1);
367}
368
369/**
370 * TODO: Doc
371 */
372template<typename X> finline
373static X bitrev(X src, if_uint(X) ) {
374 const size_t width = sizeof(X) * 8;
375 X dst = 0;
376 for (size_t i = 0; i < width; i++)
377 dst = bitset(bitget(src, i), dst, width - i - 1);
378 return dst;
379}
380
381/**
382 * TODO: Doc
383 */
384template<typename X> finline
385static void bitrev(X* src, size_t len, if_uint(X) ) {
386 for (size_t i = 0; i < len / 2; i++) {
387 bool b0 = bitget(src, i);
388 bool b1 = bitget(src, len - i - 1);
389 bitset(b1, src, i);
390 bitset(b0, src, len - i - 1);
391 }
392}
393
394/**
395 * TODO: Doc
396 */
397template<typename X> finline
398static X switch_endian(X src, if_uint(X) ) {
399 if (sizeof(X) == 1) return src;
400 X ret = 0;
401 for (size_t i = 0; i < sizeof(X); i++) {
402 ret <<= 8;
403 ret |= src & 0xFF;
404 src >>= 8;
405 }
406 return ret;
407}
408
409/**
410 * TODO: Doc
411 */
412template<typename X> finline
413static std::string bitstr(X src, int log2base = 4, if_uint(X)) {
414 const size_t word_width = sizeof(src) * 8;
415 const char digit[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
416
417 std::string str;
418 for (int i = word_width - log2base, j = 0; i >= 0; i -= log2base, j++)
419 str.append(1, digit[(src >> i) & ((1 << log2base) - 1)]);
420 return str;
421}
422
423/**
424 * TODO: Doc
425 */
426template<typename X> finline
427static std::string bitstr(X* src, size_t len, int log2base = 4, bool dot =
428 false, if_uint(X)) {
429 std::string str;
430 for (size_t i = 0; i < len / 8 / sizeof(X); i++) {
431 if (i != 0 && dot) str.append(".");
432 str.append(bitstr(src[i], log2base));
433 }
434 return str;
435}
436
437#endif /* DATAUTILITIES_HPP_ */
Note: See TracBrowser for help on using the repository browser.