vppinfra/vppinfra/zvec.c

   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 zvec_decode (uword coding, uword zdata, uword * n_zdata_bits)
  64 {
  65   uword c, d, result, n_bits;
  66   uword explicit_end, implicit_end;
  67
  68   result = 0;
  69   n_bits = 0;
  70   while (1)
  71     {
  72       c = first_set (coding);
  73       implicit_end = c == coding;
  74       explicit_end = (zdata & 1) &~ implicit_end;
  75       d = (zdata >> explicit_end) & (c - 1);
  76       if (explicit_end | implicit_end)
  77         {
  78           result += d;
  79           n_bits += min_log2 (c) + explicit_end;
  80           break;
  81         }
  82       n_bits += 1;
  83       result += c;
  84       coding ^= c;
  85       zdata >>= 1;
  86     }
  87
  88   if (coding == 0)
  89     n_bits = BITS (uword);
  90
  91   *n_zdata_bits = n_bits;
  92   return result;
  93 }
  94
  95 uword
  96 zvec_encode (uword coding,
  97              uword data,
  98              uword * n_result_bits)
  99 {
 100   uword c, shift, result;
 101   uword explicit_end, implicit_end;
 102
 103   /* Data must be in range.  Note special coding == 0
 104      would break for data - 1 <= coding. */
 105   ASSERT (data <= coding - 1);
 106
 107   shift = 0;
 108   while (1)
 109     {
 110       c = first_set (coding);
 111       implicit_end = c == coding;
 112       explicit_end = ((data & (c - 1)) == data);
 113       if (explicit_end | implicit_end)
 114         {
 115           uword t = explicit_end &~ implicit_end;
 116           result = ((data << t) | t) << shift;
 117           *n_result_bits =
 118             /* data bits */ (c == 0 ? BITS (uword) : min_log2 (c))
 119             /* shift bits */ + shift + t;
 120           return result;
 121         }
 122       data -= c;
 123       coding ^= c;
 124       shift++;
 125     }
 126
 127   /* Never reached. */
 128   ASSERT (0);
 129   return ~0;
 130 }
 131
 132 always_inline uword
 133 get_data (void * data, uword data_bytes, uword is_signed)
 134 {
 135   if (data_bytes == 1)
 136     return is_signed ? zvec_signed_to_unsigned (*(i8 *) data) : *(u8 *) data;
 137   else if (data_bytes == 2)
 138     return is_signed ? zvec_signed_to_unsigned (*(i16 *) data) : *(u16 *) data;
 139   else if (data_bytes == 4)
 140     return is_signed ? zvec_signed_to_unsigned (*(i32 *) data) : *(u32 *) data;
 141   else if (data_bytes == 8)
 142     return is_signed ? zvec_signed_to_unsigned (*(i64 *) data) : *(u64 *) data;
 143   else
 144     {
 145       os_panic ();
 146       return ~0;
 147     }
 148 }
 149
 150 always_inline void
 151 put_data (void * data, uword data_bytes, uword is_signed, uword x)
 152 {
 153   if (data_bytes == 1)
 154     {
 155       if (is_signed)
 156         *(i8 *) data = zvec_unsigned_to_signed (x);
 157       else
 158         *(u8 *) data = x;
 159     }
 160   else if (data_bytes == 2)
 161     {
 162       if (is_signed)
 163         *(i16 *) data = zvec_unsigned_to_signed (x);
 164       else
 165         *(u16 *) data = x;
 166     }
 167   else if (data_bytes == 4)
 168     {
 169       if (is_signed)
 170         *(i32 *) data = zvec_unsigned_to_signed (x);
 171       else
 172         *(u32 *) data = x;
 173     }
 174   else if (data_bytes == 8)
 175     {
 176       if (is_signed)
 177         *(i64 *) data = zvec_unsigned_to_signed (x);
 178       else
 179         *(u64 *) data = x;
 180     }
 181   else
 182     {
 183       os_panic ();
 184     }
 185 }
 186
 187 always_inline uword *
 188 zvec_encode_inline (uword * zvec,
 189                     uword * zvec_n_bits,
 190                     uword coding,
 191                     void * data,
 192                     uword data_stride,
 193                     uword n_data,
 194                     uword data_bytes,
 195                     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
 243 always_inline uword
 244 coding_max_n_bits (uword coding)
 245 {
 246   uword n_bits;
 247   (void) zvec_decode (coding, 0, &n_bits);
 248   return n_bits;
 249 }
 250
 251 always_inline void
 252 zvec_decode_inline (uword * zvec,
 253                     uword * zvec_n_bits,
 254                     uword coding,
 255                     void * data,
 256                     uword data_stride,
 257                     uword n_data,
 258                     uword data_bytes,
 259                     uword is_signed)
 260 {
 261   uword i, n_max;
 262
 263   i = *zvec_n_bits;
 264   n_max = coding_max_n_bits (coding);
 265   while (n_data >= 1)
 266     {
 267       uword d0, z0, l0;
 268
 269       z0 = clib_bitmap_get_multiple (zvec, i, n_max);
 270       d0 = zvec_decode (coding, z0, &l0);
 271       i += l0;
 272       put_data (data + 0*data_stride, data_bytes, is_signed, d0);
 273       data += 1*data_stride;
 274       n_data -= 1;
 275     }
 276   *zvec_n_bits = i;
 277 }
 278
 279 #define _(TYPE,IS_SIGNED)                                       \
 280   void zvec_decode_##TYPE (uword * zvec,                        \
 281                            uword * zvec_n_bits,                 \
 282                            uword coding,                        \
 283                            void * data,                         \
 284                            uword data_stride,                   \
 285                            uword n_data)                        \
 286   {                                                             \
 287     return zvec_decode_inline (zvec, zvec_n_bits,               \
 288                                coding,                          \
 289                                data, data_stride, n_data,       \
 290                                /* data_bytes */ sizeof (TYPE),  \
 291                                /* is_signed */ IS_SIGNED);      \
 292   }
 293
 294 _ (u8,  /* is_signed */ 0);
 295 _ (u16, /* is_signed */ 0);
 296 _ (u32, /* is_signed */ 0);
 297 _ (u64, /* is_signed */ 0);
 298 _ (i8,  /* is_signed */ 1);
 299 _ (i16, /* is_signed */ 1);
 300 _ (i32, /* is_signed */ 1);
 301 _ (i64, /* is_signed */ 1);
 302
 303 #undef _
 304
 305 /* Compute number of bits needed to encode given histogram. */
 306 static uword zvec_coding_bits (uword coding,
 307                                uword * histogram_counts,
 308                                uword min_bits)
 309 {
 310   uword n_type_bits, n_bits;
 311   uword this_count, last_count, max_count_index;
 312   uword i, b, l;
 313
 314   n_bits = 0;
 315   n_type_bits = 1;
 316   last_count = 0;
 317   max_count_index = vec_len (histogram_counts) - 1;
 318
 319   /* Coding is not large enough to encode given data. */
 320   if (coding <= max_count_index)
 321     return ~0;
 322
 323   i = 0;
 324   while (coding != 0)
 325     {
 326       b = first_set (coding);
 327       l = min_log2 (b);
 328       i += b;
 329
 330       this_count = histogram_counts[i > max_count_index ? max_count_index : i-1];
 331
 332       /* No more data to encode? */
 333       if (this_count == last_count)
 334         break;
 335
 336       /* Last coding is i 0 ... 0 so we don't need an extra type bit. */
 337       if (coding == b)
 338         n_type_bits--;
 339
 340       n_bits += (this_count - last_count) * (n_type_bits + l);
 341
 342       /* This coding cannot be minimal: so return. */
 343       if (n_bits >= min_bits)
 344         return ~0;
 345
 346       last_count = this_count;
 347       coding ^= b;
 348       n_type_bits++;
 349     }
 350
 351   return n_bits;
 352 }
 353
 354 uword
 355 _zvec_coding_from_histogram (void * histogram,
 356                              uword histogram_len,
 357                              uword histogram_elt_count_offset,
 358                              uword histogram_elt_bytes,
 359                              uword max_value_to_encode,
 360                              zvec_coding_info_t * coding_return)
 361 {
 362   uword coding, min_coding;
 363   uword min_coding_bits, coding_bits;
 364   uword i, n_bits_set, total_count;
 365   uword * counts;
 366   zvec_histogram_count_t * h_count = histogram + histogram_elt_count_offset;
 367
 368   if (histogram_len < 1)
 369     {
 370       coding_return->coding = 0;
 371       coding_return->min_coding_bits = 0;
 372       coding_return->n_data = 0;
 373       coding_return->n_codes = 0;
 374       coding_return->ave_coding_bits = 0;
 375       return 0;
 376     }
 377
 378   total_count = 0;
 379   counts = vec_new (uword, histogram_len);
 380   for (i = 0; i < histogram_len; i++)
 381     {
 382       zvec_histogram_count_t this_count = h_count[0];
 383       total_count += this_count;
 384       counts[i] = total_count;
 385       h_count = (zvec_histogram_count_t *) ((void *) h_count + histogram_elt_bytes);
 386     }
 387
 388   min_coding = 0;
 389   min_coding_bits = ~0;
 390
 391   {
 392     uword base_coding = max_value_to_encode != ~0 ? (1 + max_value_to_encode) : vec_len (counts);
 393     uword max_coding = max_pow2 (2 * base_coding);
 394
 395     for (n_bits_set = 1; n_bits_set <= 8; n_bits_set++)
 396       {
 397         for (coding = pow2_mask (n_bits_set);
 398              coding < max_coding;
 399              coding = next_with_same_number_of_set_bits (coding))
 400           {
 401             coding_bits = zvec_coding_bits (coding, counts, min_coding_bits);
 402             if (coding_bits >= min_coding_bits)
 403               continue;
 404             min_coding_bits = coding_bits;
 405             min_coding = coding;
 406           }
 407       }
 408   }
 409
 410   if (coding_return)
 411     {
 412       coding_return->coding = min_coding;
 413       coding_return->min_coding_bits = min_coding_bits;
 414       coding_return->n_data = total_count;
 415       coding_return->n_codes = vec_len (counts);
 416       coding_return->ave_coding_bits = (f64) min_coding_bits / (f64) total_count;
 417     }
 418
 419   vec_free (counts);
 420
 421   return min_coding;
 422 }
 423
 424 u8 * format_zvec_coding (u8 * s, va_list * args)
 425 {
 426   zvec_coding_info_t * c = va_arg (*args, zvec_coding_info_t *);
 427   return format (s, "zvec coding 0x%x, %d elts, %d codes, %d bits total, %.4f ave bits/code",
 428                  c->coding, c->n_data, c->n_codes, c->min_coding_bits, c->ave_coding_bits);
 429 }