An Overlay-based
Virtual Network Substrate
SpoVNet

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

Last change on this file since 7523 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.