close Warning: Can't use blame annotator: 
No changeset 2259 in the repository

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

Last change on this file since 3057 was 3057, checked in by Christoph Mayer, 16 years ago

-fixes #4 (merge tidy interface with current implementation)
File size: 10.6 KB
RevLine 
1// [Licence]
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// [Licence]
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
73/**
74 * TODO: Doc
75 */
76template<typename X> finline
77static X bitblk(size_t index, size_t length, bool value, if_uint(X)) {
78 if (index == 0 && length >= sizeof(X) * 8) return value ? ~0 : 0;
79 X x = ((((X) 1) << length) - 1) << index;
80 return value ? x : ~x;
81}
82
83/**
84 * TODO: Doc
85 */
86template<typename X, bool value> finline
87static X bitblk(size_t index, size_t length, if_uint(X)) {
88 return bitblk<X> (index, length, value);
89}
90
91/**
92 * TODO: Doc
93 */
94template<typename X, bool value> finline
95static X bitblk(size_t length, if_uint(X)) {
96 if (length >= sizeof(X) * 8) return value ? ~0 : 0;
97 return value ? (((X) 1 << length) - 1) : ~(((X) 1 << length) - 1);
98}
99
100/**
101 * This method copies bits from one integral to another
102 */
103template<typename X, typename Y> finline
104static Y bitcpy(X src, size_t srcIdx, Y dst, size_t dstIdx, size_t len =
105 sizeof(X) * 8, bool srcInvert = false, bool dstInvert = false,
106 if_uint(X),if_uint (Y) ) {
107 if (srcInvert) srcIdx = sizeof(X) * 8 - srcIdx - len;
108 if (dstInvert) dstIdx = sizeof(Y) * 8 - dstIdx - len;
109 Y value = ((Y) (src >> srcIdx)) << dstIdx;
110 Y mask = bitblk<Y, 0> (dstIdx, len);
111 return (dst & mask) | (value & ~mask);
112}
113
114/**
115 * This method copies bits from an array to another of the same
116 * integral type.
117 */
118template<typename X> finline
119static void bitcpy(X* src, size_t srcIdx, X* dst, size_t dstIdx, size_t len) {
120
121 // word width
122 const size_t w = sizeof(X) * 8;
123
124 // calculate indexes
125 size_t dwp = dstIdx % w, swp = srcIdx % w;
126 size_t idwp = w - dwp, iswp = w - swp;
127 dst += dstIdx / w;
128 src += srcIdx / w;
129
130 // check direct copy
131 if (dwp == 0 && swp == 0 && len % w == 0) {
132 memcpy(dst, src, len / 8);
133 return;
134 }
135
136 // check if first word only is affected
137 if ((dwp + len) <= w) {
138 X fw = (src[0] << swp) | (src[1] >> iswp);
139 *dst = bitcpy(fw, 0, *dst, dwp, len, true, true);
140 return;
141 }
142
143 // set first word
144 if (idwp != 0) {
145 X fw = (src[0] << swp) | (src[1] >> iswp);
146 *dst = (*dst & ~(((X) 1 << idwp) - 1)) | (fw >> dwp);
147
148 // recalculate indexes & lengths
149 dst++;
150 src++;
151 len -= idwp;
152 swp = (swp + idwp) % w;
153 iswp = w - swp;
154 }
155
156 X a, b;
157
158 // copy whole words
159 if (swp == 0) {
160 size_t numWords = len / w;
161 // use memory copy
162 memcpy(dst, src, numWords * sizeof(X));
163 src += numWords;
164 dst += numWords;
165 len = len % w;
166 a = src[0], b = src[1];
167 } else {
168 // use shifted copy
169 a = src[0], b = src[1];
170 while (len >= w) {
171 *dst = (a << swp) | (b >> iswp);
172 dst++;
173 src++;
174 len -= w;
175 a = b;
176 b = *src;
177 }
178 }
179
180 // set last word
181 X lw = (a << swp) | (b >> iswp), lm = (((X) 1 << (w - len)) - 1);
182 *dst = (*dst & lm) | (lw & ~lm);
183}
184
185/**
186 * array -> integral
187 */
188template<typename X, typename Y> finline
189static void bitcpy(X* src, size_t srcIdx, Y& dst, size_t dstIdx, size_t len =
190 sizeof(Y) * 8, if_uint(Y),if_uint (X) ) {
191
192 // word width
193 const size_t w = sizeof(X) * 8;
194
195 // calculate indexes
196 size_t swp = srcIdx % w, iswp = w - swp;
197 src += srcIdx / w;
198
199 // mask off bits
200 dst &= bitblk<Y,0>(dstIdx,len);
201
202 // copy whole words
203 X a = src[0], b = src[1];
204 Y value = 0;
205 src++;
206 while (len >= w) {
207 X x = (a << swp) | (b >> iswp);
208 value <<= w;
209 value |= x;
210 src++;
211 len -= w;
212 a = b; b = *src;
213 }
214
215 // copy leftover
216 if ( len> 0 ) {
217 value <<= len;
218 value |= (((a << swp) | (b >> iswp)) >> (w - len)) & ((1 << len)-1);
219 }
220
221 // set value
222 dst |= (value << dstIdx);
223 }
224
225/**
226 * TODO: Doc
227 */
228// word -> array
229template<typename X> finline
230static void bitcpy(X src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =
231 sizeof(X) * 8, bool srcInvert = false, if_uint(X)) {
232
233 // check inversion
234 if (srcInvert) srcIdx = sizeof(X) * 8 - srcIdx - len;
235
236 // word width
237 const size_t w = sizeof(X) * 8;
238
239 // calculate indexes
240 size_t dwp = dstIdx % w;
241 dst += dstIdx / w;
242
243 // copy directly
244 if (dwp == 0 && srcIdx == 0 && len == w) {
245 *dst = src;
246 } else
247
248 // copy non-overlapping word
249 if ((dwp + len) <= w) {
250 *dst = bitcpy(src, srcIdx, *dst, dwp, len, false, true);
251
252 // copy overlapping word
253 } else {
254 size_t idwp = w - dwp;
255 src >>= srcIdx;
256 X mask1 = ~((1 << idwp) - 1);
257 dst[0] = (dst[0] & mask1) | ((src >> (len - idwp)) & ~mask1);
258 X mask2 = (1 << (w - len + idwp)) - 1;
259 dst[1] = (dst[1] & mask2) | ((src << (w - len + idwp)) & ~mask2);
260 }
261}
262
263/**
264 * TODO: Doc
265 */
266// integral -> array
267template<typename Y, typename X> finline
268static void bitcpy(Y src, size_t srcIdx, X* dst, size_t dstIdx, size_t len =
269 sizeof(Y) * 8, bool srcInvert = false, if_uint(X),if_uint (Y) ) {
270
271 if (sizeof(Y) <= sizeof(X)) {
272 // check inversion
273 if (srcInvert)
274 srcIdx = sizeof(Y) * 8 - srcIdx - len + (sizeof(X)-sizeof(Y))*8;
275 bitcpy((X)src,srcIdx,dst,dstIdx,len,false);
276 } else {
277 // check inversion
278 if (srcInvert) srcIdx = sizeof(Y) * 8 - srcIdx - len;
279 src >>= srcIdx;
280
281 const size_t dw = sizeof(X)*8;
282 while (len >= dw) {
283 X word = (X)(src >> (len-dw));
284 bitcpy(word,0,dst,dstIdx,dw);
285 dstIdx += dw;
286 len -= dw;
287 }
288 X word = (X)src;
289 bitcpy(word,0,dst,dstIdx,len);
290 }
291}
292
293/**
294 * TODO: Doc
295 */
296template<typename T, typename X> finline
297static T bitget(X* src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {
298 T x = 0;
299 bitcpy(src, idx, x, 0, len );
300 return x;
301}
302
303/**
304 * TODO: Doc
305 */
306template<typename T, typename X> finline
307static T bitget(X src, size_t idx, size_t len = sizeof(T) * 8, if_uint(X),if_uint (T) ) {
308 T x = 0;
309 bitcpy(src, idx, x, 0, len );
310 return x;
311}
312
313/**
314 * TODO: Doc
315 */
316template<typename X> finline
317static bool bitget(X* src, size_t index, if_uint(X)) {
318 uint8_t x = 0;
319 bitcpy(src, index, x, 0, 1);
320 return x != 0;
321}
322
323/**
324 * TODO: Doc
325 */
326template<typename X> finline
327static bool bitget(X src, size_t index, if_uint(X)) {
328 uint8_t x = 0;
329 x = bitcpy(src, index, x, 0, 1);
330 return x != 0;
331}
332
333/**
334 * TODO: Doc
335 */
336template<typename T, typename X> finline
337static void bitset(T src, X* dst, size_t index, if_uint(X),if_uint (T) ) {
338 bitcpy(src,0,dst,index);
339}
340
341/**
342 * TODO: Doc
343 */
344template<typename X> finline
345static void bitset(bool src, X* dst, size_t index, if_uint(X) ) {
346 bitcpy(src != 0, 0, dst, index, 1);
347}
348
349/**
350 * TODO: Doc
351 */
352template<typename X> finline
353static X bitset(bool src, X dst, size_t index, if_uint(X)) {
354 return bitcpy(src != 0, 0, dst, index, 1);
355}
356
357/**
358 * TODO: Doc
359 */
360template<typename X> finline
361static X bitrev(X src, if_uint(X) ) {
362 const size_t width = sizeof(X) * 8;
363 X dst = 0;
364 for (size_t i = 0; i < width; i++)
365 dst = bitset(bitget(src, i), dst, width - i - 1);
366 return dst;
367}
368
369/**
370 * TODO: Doc
371 */
372template<typename X> finline
373static void bitrev(X* src, size_t len, if_uint(X) ) {
374 for (size_t i = 0; i < len / 2; i++) {
375 bool b0 = bitget(src, i);
376 bool b1 = bitget(src, len - i - 1);
377 bitset(b1, src, i);
378 bitset(b0, src, len - i - 1);
379 }
380}
381
382/**
383 * TODO: Doc
384 */
385template<typename X> finline
386static X switch_endian(X src, if_uint(X) ) {
387 if (sizeof(X) == 1) return src;
388 X ret = 0;
389 for (size_t i = 0; i < sizeof(X); i++) {
390 ret <<= 8;
391 ret |= src & 0xFF;
392 src >>= 8;
393 }
394 return ret;
395}
396
397/**
398 * TODO: Doc
399 */
400template<typename X> finline
401static std::string bitstr(X src, int log2base = 4, if_uint(X)) {
402 const size_t word_width = sizeof(src) * 8;
403 const char digit[37] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
404
405 std::string str;
406 for (int i = word_width - log2base, j = 0; i >= 0; i -= log2base, j++)
407 str.append(1, digit[(src >> i) & ((1 << log2base) - 1)]);
408 return str;
409}
410
411/**
412 * TODO: Doc
413 */
414template<typename X> finline
415static std::string bitstr(X* src, size_t len, int log2base = 4, bool dot =
416 false, if_uint(X)) {
417 std::string str;
418 for (size_t i = 0; i < len / 8 / sizeof(X); i++) {
419 if (i != 0 && dot) str.append(".");
420 str.append(bitstr(src[i], log2base));
421 }
422 return str;
423}
424
425#endif /* DATAUTILITIES_HPP_ */
Note: See TracBrowser for help on using the repository browser.