FD.io VPP  v19.01.3-6-g70449b9b9
Vector Packet Processing
zvec.c
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2015 Cisco and/or its affiliates.
3  * Licensed under the Apache License, Version 2.0 (the "License");
4  * you may not use this file except in compliance with the License.
5  * You may obtain a copy of the License at:
6  *
7  * http://www.apache.org/licenses/LICENSE-2.0
8  *
9  * Unless required by applicable law or agreed to in writing, software
10  * distributed under the License is distributed on an "AS IS" BASIS,
11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12  * See the License for the specific language governing permissions and
13  * limitations under the License.
14  */
15 /*
16  Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
17 
18  Permission is hereby granted, free of charge, to any person obtaining
19  a copy of this software and associated documentation files (the
20  "Software"), to deal in the Software without restriction, including
21  without limitation the rights to use, copy, modify, merge, publish,
22  distribute, sublicense, and/or sell copies of the Software, and to
23  permit persons to whom the Software is furnished to do so, subject to
24  the following conditions:
25 
26  The above copyright notice and this permission notice shall be
27  included in all copies or substantial portions of the Software.
28 
29  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
30  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
31  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
32  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
33  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
34  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
35  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
36 */
37 
38 #include <vppinfra/bitmap.h>
39 #include <vppinfra/bitops.h> /* for next_with_same_number_of_set_bits */
40 #include <vppinfra/error.h> /* for ASSERT */
41 #include <vppinfra/mem.h>
42 #include <vppinfra/os.h> /* for os_panic */
43 #include <vppinfra/vec.h>
44 #include <vppinfra/zvec.h>
45 
46 /* Consider coding as bitmap, coding = 2^c_0 + 2^c_1 + ... + 2^c_n
47  With c_0 < c_1 < ... < c_n. coding == 0 represents c_n = BITS (uword).
48 
49  Unsigned integers i = 0 ... are represented as follows:
50 
51  0 <= i < 2^c_0 (i << 1) | (1 << 0) binary: i 1
52  2^c_0 <= i < 2^c_0 + 2^c_1 (i << 2) | (1 << 1) binary: i 1 0
53  ... binary: i 0 ... 0
54 
55  Smaller numbers use less bits. Coding is chosen so that encoding
56  of given histogram of typical values gives smallest number of bits.
57  The number and position of coding bits c_i are used to best fit the
58  histogram of typical values.
59 */
60 
61 /* Decode given compressed data. Return number of compressed data
62  bits used. */
63 uword
64 zvec_decode (uword coding, uword zdata, uword * n_zdata_bits)
65 {
66  uword c, d, result, n_bits;
67  uword explicit_end, implicit_end;
68 
69  result = 0;
70  n_bits = 0;
71  while (1)
72  {
73  c = first_set (coding);
74  implicit_end = c == coding;
75  explicit_end = (zdata & 1) & ~implicit_end;
76  d = (zdata >> explicit_end) & (c - 1);
77  if (explicit_end | implicit_end)
78  {
79  result += d;
80  n_bits += min_log2 (c) + explicit_end;
81  break;
82  }
83  n_bits += 1;
84  result += c;
85  coding ^= c;
86  zdata >>= 1;
87  }
88 
89  if (coding == 0)
90  n_bits = BITS (uword);
91 
92  *n_zdata_bits = n_bits;
93  return result;
94 }
95 
96 uword
97 zvec_encode (uword coding, uword data, uword * n_result_bits)
98 {
99  uword c, shift, result;
100  uword explicit_end, implicit_end;
101 
102  /* Data must be in range. Note special coding == 0
103  would break for data - 1 <= coding. */
104  ASSERT (data <= coding - 1);
105 
106  shift = 0;
107  while (1)
108  {
109  c = first_set (coding);
110  implicit_end = c == coding;
111  explicit_end = ((data & (c - 1)) == data);
112  if (explicit_end | implicit_end)
113  {
114  uword t = explicit_end & ~implicit_end;
115  result = ((data << t) | t) << shift;
116  *n_result_bits =
117  /* data bits */ (c == 0 ? BITS (uword) : min_log2 (c))
118  /* shift bits */ + shift + t;
119  return result;
120  }
121  data -= c;
122  coding ^= c;
123  shift++;
124  }
125 
126  /* Never reached. */
127  ASSERT (0);
128  return ~0;
129 }
130 
132 get_data (void *data, uword data_bytes, uword is_signed)
133 {
134  if (data_bytes == 1)
135  return is_signed ? zvec_signed_to_unsigned (*(i8 *) data) : *(u8 *) data;
136  else if (data_bytes == 2)
137  return is_signed ? zvec_signed_to_unsigned (*(i16 *) data) : *(u16 *)
138  data;
139  else if (data_bytes == 4)
140  return is_signed ? zvec_signed_to_unsigned (*(i32 *) data) : *(u32 *)
141  data;
142  else if (data_bytes == 8)
143  return is_signed ? zvec_signed_to_unsigned (*(i64 *) data) : *(u64 *)
144  data;
145  else
146  {
147  os_panic ();
148  return ~0;
149  }
150 }
151 
152 always_inline void
153 put_data (void *data, uword data_bytes, uword is_signed, uword x)
154 {
155  if (data_bytes == 1)
156  {
157  if (is_signed)
158  *(i8 *) data = zvec_unsigned_to_signed (x);
159  else
160  *(u8 *) data = x;
161  }
162  else if (data_bytes == 2)
163  {
164  if (is_signed)
165  *(i16 *) data = zvec_unsigned_to_signed (x);
166  else
167  *(u16 *) data = x;
168  }
169  else if (data_bytes == 4)
170  {
171  if (is_signed)
172  *(i32 *) data = zvec_unsigned_to_signed (x);
173  else
174  *(u32 *) data = x;
175  }
176  else if (data_bytes == 8)
177  {
178  if (is_signed)
179  *(i64 *) data = zvec_unsigned_to_signed (x);
180  else
181  *(u64 *) data = x;
182  }
183  else
184  {
185  os_panic ();
186  }
187 }
188 
191  uword * zvec_n_bits,
192  uword coding,
193  void *data,
194  uword data_stride,
195  uword n_data, uword data_bytes, uword is_signed)
196 {
197  uword i;
198 
199  i = *zvec_n_bits;
200  while (n_data >= 1)
201  {
202  uword d0, z0, l0;
203 
204  d0 = get_data (data + 0 * data_stride, data_bytes, is_signed);
205  data += 1 * data_stride;
206  n_data -= 1;
207 
208  z0 = zvec_encode (coding, d0, &l0);
209  zvec = clib_bitmap_set_multiple (zvec, i, z0, l0);
210  i += l0;
211  }
212 
213  *zvec_n_bits = i;
214  return zvec;
215 }
216 
217 #define _(TYPE,IS_SIGNED) \
218  uword * zvec_encode_##TYPE (uword * zvec, \
219  uword * zvec_n_bits, \
220  uword coding, \
221  void * data, \
222  uword data_stride, \
223  uword n_data) \
224  { \
225  return zvec_encode_inline (zvec, zvec_n_bits, \
226  coding, \
227  data, data_stride, n_data, \
228  /* data_bytes */ sizeof (TYPE), \
229  /* is_signed */ IS_SIGNED); \
230  }
231 
232 _(u8, /* is_signed */ 0);
233 _(u16, /* is_signed */ 0);
234 _(u32, /* is_signed */ 0);
235 _(u64, /* is_signed */ 0);
236 _(i8, /* is_signed */ 1);
237 _(i16, /* is_signed */ 1);
238 _(i32, /* is_signed */ 1);
239 _(i64, /* is_signed */ 1);
240 
241 #undef _
242 
245 {
246  uword n_bits;
247  (void) zvec_decode (coding, 0, &n_bits);
248  return n_bits;
249 }
250 
251 always_inline void
253  uword * zvec_n_bits,
254  uword coding,
255  void *data,
256  uword data_stride,
257  uword n_data, uword data_bytes, uword is_signed)
258 {
259  uword i, n_max;
260 
261  i = *zvec_n_bits;
262  n_max = coding_max_n_bits (coding);
263  while (n_data >= 1)
264  {
265  uword d0, z0, l0;
266 
267  z0 = clib_bitmap_get_multiple (zvec, i, n_max);
268  d0 = zvec_decode (coding, z0, &l0);
269  i += l0;
270  put_data (data + 0 * data_stride, data_bytes, is_signed, d0);
271  data += 1 * data_stride;
272  n_data -= 1;
273  }
274  *zvec_n_bits = i;
275 }
276 
277 #define _(TYPE,IS_SIGNED) \
278  void zvec_decode_##TYPE (uword * zvec, \
279  uword * zvec_n_bits, \
280  uword coding, \
281  void * data, \
282  uword data_stride, \
283  uword n_data) \
284  { \
285  return zvec_decode_inline (zvec, zvec_n_bits, \
286  coding, \
287  data, data_stride, n_data, \
288  /* data_bytes */ sizeof (TYPE), \
289  /* is_signed */ IS_SIGNED); \
290  }
291 
292 _(u8, /* is_signed */ 0);
293 _(u16, /* is_signed */ 0);
294 _(u32, /* is_signed */ 0);
295 _(u64, /* is_signed */ 0);
296 _(i8, /* is_signed */ 1);
297 _(i16, /* is_signed */ 1);
298 _(i32, /* is_signed */ 1);
299 _(i64, /* is_signed */ 1);
300 
301 #undef _
302 
303 /* Compute number of bits needed to encode given histogram. */
304 static uword
305 zvec_coding_bits (uword coding, uword * histogram_counts, uword min_bits)
306 {
307  uword n_type_bits, n_bits;
308  uword this_count, last_count, max_count_index;
309  uword i, b, l;
310 
311  n_bits = 0;
312  n_type_bits = 1;
313  last_count = 0;
314  max_count_index = vec_len (histogram_counts) - 1;
315 
316  /* Coding is not large enough to encode given data. */
317  if (coding <= max_count_index)
318  return ~0;
319 
320  i = 0;
321  while (coding != 0)
322  {
323  b = first_set (coding);
324  l = min_log2 (b);
325  i += b;
326 
327  this_count =
328  histogram_counts[i > max_count_index ? max_count_index : i - 1];
329 
330  /* No more data to encode? */
331  if (this_count == last_count)
332  break;
333 
334  /* Last coding is i 0 ... 0 so we don't need an extra type bit. */
335  if (coding == b)
336  n_type_bits--;
337 
338  n_bits += (this_count - last_count) * (n_type_bits + l);
339 
340  /* This coding cannot be minimal: so return. */
341  if (n_bits >= min_bits)
342  return ~0;
343 
344  last_count = this_count;
345  coding ^= b;
346  n_type_bits++;
347  }
348 
349  return n_bits;
350 }
351 
352 uword
353 _zvec_coding_from_histogram (void *histogram,
354  uword histogram_len,
355  uword histogram_elt_count_offset,
356  uword histogram_elt_bytes,
357  uword max_value_to_encode,
358  zvec_coding_info_t * coding_return)
359 {
360  uword coding, min_coding;
361  uword min_coding_bits, coding_bits;
362  uword i, n_bits_set, total_count;
363  uword *counts;
364  zvec_histogram_count_t *h_count = histogram + histogram_elt_count_offset;
365 
366  if (histogram_len < 1)
367  {
368  coding_return->coding = 0;
369  coding_return->min_coding_bits = 0;
370  coding_return->n_data = 0;
371  coding_return->n_codes = 0;
372  coding_return->ave_coding_bits = 0;
373  return 0;
374  }
375 
376  total_count = 0;
377  counts = vec_new (uword, histogram_len);
378  for (i = 0; i < histogram_len; i++)
379  {
380  zvec_histogram_count_t this_count = h_count[0];
381  total_count += this_count;
382  counts[i] = total_count;
383  h_count =
384  (zvec_histogram_count_t *) ((void *) h_count + histogram_elt_bytes);
385  }
386 
387  min_coding = 0;
388  min_coding_bits = ~0;
389 
390  {
391  uword base_coding =
392  max_value_to_encode !=
393  ~0 ? (1 + max_value_to_encode) : vec_len (counts);
394  uword max_coding = max_pow2 (2 * base_coding);
395 
396  for (n_bits_set = 1; n_bits_set <= 8; n_bits_set++)
397  {
398  for (coding = pow2_mask (n_bits_set);
399  coding < max_coding;
400  coding = next_with_same_number_of_set_bits (coding))
401  {
402  coding_bits = zvec_coding_bits (coding, counts, min_coding_bits);
403  if (coding_bits >= min_coding_bits)
404  continue;
405  min_coding_bits = coding_bits;
406  min_coding = coding;
407  }
408  }
409  }
410 
411  if (coding_return)
412  {
413  coding_return->coding = min_coding;
414  coding_return->min_coding_bits = min_coding_bits;
415  coding_return->n_data = total_count;
416  coding_return->n_codes = vec_len (counts);
417  coding_return->ave_coding_bits =
418  (f64) min_coding_bits / (f64) total_count;
419  }
420 
421  vec_free (counts);
422 
423  return min_coding;
424 }
425 
426 u8 *
427 format_zvec_coding (u8 * s, va_list * args)
428 {
429  zvec_coding_info_t *c = va_arg (*args, zvec_coding_info_t *);
430  return format (s,
431  "zvec coding 0x%x, %d elts, %d codes, %d bits total, %.4f ave bits/code",
432  c->coding, c->n_data, c->n_codes, c->min_coding_bits,
433  c->ave_coding_bits);
434 }
435 
436 /*
437  * fd.io coding-style-patch-verification: ON
438  *
439  * Local Variables:
440  * eval: (c-set-style "gnu")
441  * End:
442  */
static void zvec_decode_inline(uword *zvec, uword *zvec_n_bits, uword coding, void *data, uword data_stride, uword n_data, uword data_bytes, uword is_signed)
Definition: zvec.c:252
unsigned long u64
Definition: types.h:89
void os_panic(void)
Definition: unix-misc.c:174
int i
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:419
unsigned char u8
Definition: types.h:56
static uword min_log2(uword x)
Definition: clib.h:144
double f64
Definition: types.h:142
f64 ave_coding_bits
Definition: zvec.h:79
#define always_inline
Definition: clib.h:98
static uword pow2_mask(uword x)
Definition: clib.h:220
#define vec_new(T, N)
Create new vector of given type and length (unspecified alignment, no header).
Definition: vec.h:311
uword zvec_decode(uword coding, uword zdata, uword *n_zdata_bits)
Definition: zvec.c:64
uword zvec_encode(uword coding, uword data, uword *n_result_bits)
Definition: zvec.c:97
unsigned int u32
Definition: types.h:88
static void put_data(void *data, uword data_bytes, uword is_signed, uword x)
Definition: zvec.c:153
unsigned short u16
Definition: types.h:57
signed long i64
Definition: types.h:78
static uword zvec_signed_to_unsigned(word s)
Definition: zvec.h:143
static uword * zvec_encode_inline(uword *zvec, uword *zvec_n_bits, uword coding, void *data, uword data_stride, uword n_data, uword data_bytes, uword is_signed)
Definition: zvec.c:190
signed char i8
Definition: types.h:45
static uword clib_bitmap_get_multiple(uword *bitmap, uword i, uword n_bits)
Gets the ith through ith + n_bits bit values from a bitmap.
Definition: bitmap.h:235
u32 zvec_histogram_count_t
Definition: zvec.h:88
svmdb_client_t * c
#define vec_free(V)
Free vector&#39;s memory (no header).
Definition: vec.h:341
static uword max_pow2(uword x)
Definition: clib.h:226
static uword * clib_bitmap_set_multiple(uword *bitmap, uword i, uword value, uword n_bits)
sets the ith through ith + n_bits bits in a bitmap
Definition: bitmap.h:275
signed int i32
Definition: types.h:77
static uword first_set(uword x)
Definition: clib.h:253
#define ASSERT(truth)
static uword coding_max_n_bits(uword coding)
Definition: zvec.c:244
static uword get_data(void *data, uword data_bytes, uword is_signed)
Definition: zvec.c:132
Bitmaps built as vectors of machine words.
static word zvec_unsigned_to_signed(uword u)
Definition: zvec.h:151
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
u64 uword
Definition: types.h:112
static uword zvec_coding_bits(uword coding, uword *histogram_counts, uword min_bits)
Definition: zvec.c:305
u32 min_coding_bits
Definition: zvec.h:76
#define BITS(x)
Definition: clib.h:61
u8 * format_zvec_coding(u8 *s, va_list *args)
Definition: zvec.c:427
static uword next_with_same_number_of_set_bits(uword x)
Definition: bitops.h:156
CLIB vectors are ubiquitous dynamically resized arrays with by user defined "headers".
signed short i16
Definition: types.h:46