GCS  0.2.3
gu_vlq.hpp
1 //
2 // Copyright (C) 2011-2013 Codership Oy <info@codership.com>
3 //
4 
6 // @file Variable-length quantity encoding for integers
7 //
8 // Unsigned integers: Implementation uses using unsigned LEB128,
9 // see for example http://en.wikipedia.org/wiki/LEB128.
10 //
11 // Signed integers: TODO
12 //
13 
14 #ifndef GU_VLQ_HPP
15 #define GU_VLQ_HPP
16 
17 #include "gu_buffer.hpp"
18 #include "gu_throw.hpp"
19 
20 #include "gu_macros.h"
21 
22 #define GU_VLQ_CHECKS
23 #define GU_VLQ_ALEX
24 
25 namespace gu
26 {
28  // @brief Retun number of bytes required to represent given value in ULEB128
29  // representation.
30  //
31  // @param value Unsigned value
32  //
33  // @return Number of bytes required for value representation
34  //
35  template <typename UI>
36  inline size_t uleb128_size(UI value)
37  {
38  size_t i(1);
39  value >>= 7;
40 
41  for (; value != 0; value >>= 7, ++i) {}
42 
43  return i;
44  }
45 
47  // @brief Encode unsigned type to ULEB128 representation
48  //
49  // @param value
50  // @param buf
51  // @param buflen
52  // @param offset
53  //
54  // @return Offset
55  //
56  template <typename UI>
57  inline size_t uleb128_encode(UI value,
58  byte_t* buf,
59  size_t buflen,
60  size_t offset)
61  {
62 #ifdef GU_VLQ_ALEX
63  assert (offset < buflen);
64  buf[offset] = value & 0x7f;
65 
66  while (value >>= 7)
67  {
68  buf[offset] |= 0x80;
69  ++offset;
70 #ifdef GU_VLQ_CHECKS
71  if (gu_unlikely(offset >= buflen)) gu_throw_fatal;
72 #else
73  assert(offset < buflen);
74 #endif /* GU_VLQ_CHECKS */
75  buf[offset] = value & 0x7f;
76  }
77 
78  return offset + 1;
79 #else /* GU_VLQ_ALEX */
80  do
81  {
82 #ifdef GU_VLQ_CHECKS
83  if (gu_unlikely(offset >= buflen)) gu_throw_fatal;
84 #else
85  assert(offset < buflen);
86 #endif /* GU_VLQ_CHECKS */
87  buf[offset] = value & 0x7f;
88  value >>= 7;
89  if (gu_unlikely(value != 0))
90  {
91  buf[offset] |= 0x80;
92  }
93  ++offset;
94  }
95  while (value != 0);
96 
97  return offset;
98 #endif /* GU_VLQ_ALEX */
99  }
100 
101  template <typename UI>
102  inline size_t uleb128_encode(UI value,
103  byte_t* buf,
104  size_t buflen)
105  {
106  return uleb128_encode(value, buf, buflen, 0);
107  }
108 
109 
110  /* checks helper for the uleb128_decode() below */
111  extern void uleb128_decode_checks (const byte_t* buf,
112  size_t buflen,
113  size_t offset,
114  size_t avail_bits);
115 
117  // @brief Decode unsigned type from ULEB128 representation
118  //
119  // @param buf
120  // @param buflen
121  // @param offset
122  // @param value
123  //
124  // @return Offset
125  //
126  template <typename UI>
127  inline size_t uleb128_decode(const byte_t* buf,
128  size_t buflen,
129  size_t offset,
130  UI& value)
131  {
132  // initial check for overflow, at least one byte must be readable
133 #ifdef GU_VLQ_CHECKS
134  if (gu_unlikely(offset >= buflen)) gu_throw_fatal;
135 #endif
136 
137 #ifdef GU_VLQ_ALEX
138  value = buf[offset] & 0x7f;
139  size_t shift(0);
140 
141  while (buf[offset] & 0x80)
142  {
143  ++offset;
144  shift +=7;
145 
146 #ifdef GU_VLQ_CHECKS
147  ssize_t left_bits((sizeof(UI) << 3) - shift);
148  if (gu_unlikely(offset >= buflen || left_bits < 7))
149  uleb128_decode_checks (buf, buflen, offset, left_bits);
150 #endif
151  value |= (UI(buf[offset] & 0x7f) << shift);
152  }
153 
154  return offset + 1;
155 #else /* GU_VLQ_ALEX */
156  value = 0;
157  size_t shift(0);
158 
159  while (true)
160  {
161  value |= (UI(buf[offset] & 0x7f) << shift);
162  if (gu_likely((buf[offset] & 0x80) == 0))
163  {
164  // last byte
165  ++offset;
166  break;
167  }
168  ++offset;
169  shift += 7;
170 
171 #ifdef GU_VLQ_CHECKS
172  ssize_t left_bits((sizeof(UI) << 3) - shift);
173  if (gu_unlikely(offset >= buflen || left_bits < 7))
174  uleb128_decode_checks (buf, buflen, offset, left_bits);
175 #endif
176  }
177 
178  return offset;
179 #endif /* GU_VLQ_ALEX */
180  }
181 
182  template <typename UI>
183  inline size_t uleb128_decode(const byte_t* buf,
184  size_t buflen,
185  UI& value)
186  {
187  return uleb128_decode(buf, buflen, 0, value);
188  }
189 }
190 
191 #endif // GU_VLQ_HPP