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
  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
 131 always_inline uword
 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
 189 always_inline uword *
 190 zvec_encode_inline (uword * zvec,
 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
 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, 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  */