An Overlay-based
Virtual Network Substrate
SpoVNet

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

Last change on this file since 2378 was 2378, checked in by Christoph Mayer, 15 years ago

Renamed remotely

File size: 10.6 KB
Line 
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.