summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/zvec.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/vppinfra/zvec.c')
-rw-r--r--src/vppinfra/zvec.c442
1 files changed, 0 insertions, 442 deletions
diff --git a/src/vppinfra/zvec.c b/src/vppinfra/zvec.c
deleted file mode 100644
index d062e5f7db1..00000000000
--- a/src/vppinfra/zvec.c
+++ /dev/null
@@ -1,442 +0,0 @@
-/*
- * Copyright (c) 2015 Cisco and/or its affiliates.
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * You may obtain a copy of the License at:
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-/*
- Copyright (c) 2001, 2002, 2003, 2005 Eliot Dresselhaus
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be
- included in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
- LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
- OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
- WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
-
-#include <vppinfra/bitmap.h>
-#include <vppinfra/bitops.h> /* for next_with_same_number_of_set_bits */
-#include <vppinfra/error.h> /* for ASSERT */
-#include <vppinfra/mem.h>
-#include <vppinfra/os.h> /* for os_panic */
-#include <vppinfra/vec.h>
-#include <vppinfra/zvec.h>
-
-/* Consider coding as bitmap, coding = 2^c_0 + 2^c_1 + ... + 2^c_n
- With c_0 < c_1 < ... < c_n. coding == 0 represents c_n = BITS (uword).
-
- Unsigned integers i = 0 ... are represented as follows:
-
- 0 <= i < 2^c_0 (i << 1) | (1 << 0) binary: i 1
- 2^c_0 <= i < 2^c_0 + 2^c_1 (i << 2) | (1 << 1) binary: i 1 0
- ... binary: i 0 ... 0
-
- Smaller numbers use less bits. Coding is chosen so that encoding
- of given histogram of typical values gives smallest number of bits.
- The number and position of coding bits c_i are used to best fit the
- histogram of typical values.
-*/
-
-/* Decode given compressed data. Return number of compressed data
- bits used. */
-uword
-zvec_decode (uword coding, uword zdata, uword * n_zdata_bits)
-{
- uword c, d, result, n_bits;
- uword explicit_end, implicit_end;
-
- result = 0;
- n_bits = 0;
- while (1)
- {
- c = first_set (coding);
- implicit_end = c == coding;
- explicit_end = (zdata & 1) & ~implicit_end;
- d = (zdata >> explicit_end) & (c - 1);
- if (explicit_end | implicit_end)
- {
- result += d;
- n_bits += min_log2 (c) + explicit_end;
- break;
- }
- n_bits += 1;
- result += c;
- coding ^= c;
- zdata >>= 1;
- }
-
- if (coding == 0)
- n_bits = BITS (uword);
-
- *n_zdata_bits = n_bits;
- return result;
-}
-
-uword
-zvec_encode (uword coding, uword data, uword * n_result_bits)
-{
- uword c, shift, result;
- uword explicit_end, implicit_end;
-
- /* Data must be in range. Note special coding == 0
- would break for data - 1 <= coding. */
- ASSERT (data <= coding - 1);
-
- shift = 0;
- while (1)
- {
- c = first_set (coding);
- implicit_end = c == coding;
- explicit_end = ((data & (c - 1)) == data);
- if (explicit_end | implicit_end)
- {
- uword t = explicit_end & ~implicit_end;
- result = ((data << t) | t) << shift;
- *n_result_bits =
- /* data bits */ (c == 0 ? BITS (uword) : min_log2 (c))
- /* shift bits */ + shift + t;
- return result;
- }
- data -= c;
- coding ^= c;
- shift++;
- }
-
- /* Never reached. */
- ASSERT (0);
- return ~0;
-}
-
-always_inline uword
-get_data (void *data, uword data_bytes, uword is_signed)
-{
- if (data_bytes == 1)
- return is_signed ? zvec_signed_to_unsigned (*(i8 *) data) : *(u8 *) data;
- else if (data_bytes == 2)
- return is_signed ? zvec_signed_to_unsigned (*(i16 *) data) : *(u16 *)
- data;
- else if (data_bytes == 4)
- return is_signed ? zvec_signed_to_unsigned (*(i32 *) data) : *(u32 *)
- data;
- else if (data_bytes == 8)
- return is_signed ? zvec_signed_to_unsigned (*(i64 *) data) : *(u64 *)
- data;
- else
- {
- os_panic ();
- return ~0;
- }
-}
-
-always_inline void
-put_data (void *data, uword data_bytes, uword is_signed, uword x)
-{
- if (data_bytes == 1)
- {
- if (is_signed)
- *(i8 *) data = zvec_unsigned_to_signed (x);
- else
- *(u8 *) data = x;
- }
- else if (data_bytes == 2)
- {
- if (is_signed)
- *(i16 *) data = zvec_unsigned_to_signed (x);
- else
- *(u16 *) data = x;
- }
- else if (data_bytes == 4)
- {
- if (is_signed)
- *(i32 *) data = zvec_unsigned_to_signed (x);
- else
- *(u32 *) data = x;
- }
- else if (data_bytes == 8)
- {
- if (is_signed)
- *(i64 *) data = zvec_unsigned_to_signed (x);
- else
- *(u64 *) data = x;
- }
- else
- {
- os_panic ();
- }
-}
-
-always_inline 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)
-{
- uword i;
-
- i = *zvec_n_bits;
- while (n_data >= 1)
- {
- uword d0, z0, l0;
-
- d0 = get_data (data + 0 * data_stride, data_bytes, is_signed);
- data += 1 * data_stride;
- n_data -= 1;
-
- z0 = zvec_encode (coding, d0, &l0);
- zvec = clib_bitmap_set_multiple (zvec, i, z0, l0);
- i += l0;
- }
-
- *zvec_n_bits = i;
- return zvec;
-}
-
-#define _(TYPE,IS_SIGNED) \
- uword * zvec_encode_##TYPE (uword * zvec, \
- uword * zvec_n_bits, \
- uword coding, \
- void * data, \
- uword data_stride, \
- uword n_data) \
- { \
- return zvec_encode_inline (zvec, zvec_n_bits, \
- coding, \
- data, data_stride, n_data, \
- /* data_bytes */ sizeof (TYPE), \
- /* is_signed */ IS_SIGNED); \
- }
-
-_(u8, /* is_signed */ 0);
-_(u16, /* is_signed */ 0);
-_(u32, /* is_signed */ 0);
-_(u64, /* is_signed */ 0);
-_(i8, /* is_signed */ 1);
-_(i16, /* is_signed */ 1);
-_(i32, /* is_signed */ 1);
-_(i64, /* is_signed */ 1);
-
-#undef _
-
-always_inline uword
-coding_max_n_bits (uword coding)
-{
- uword n_bits;
- (void) zvec_decode (coding, 0, &n_bits);
- return n_bits;
-}
-
-always_inline 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)
-{
- uword i, n_max;
-
- i = *zvec_n_bits;
- n_max = coding_max_n_bits (coding);
- while (n_data >= 1)
- {
- uword d0, z0, l0;
-
- z0 = clib_bitmap_get_multiple (zvec, i, n_max);
- d0 = zvec_decode (coding, z0, &l0);
- i += l0;
- put_data (data + 0 * data_stride, data_bytes, is_signed, d0);
- data += 1 * data_stride;
- n_data -= 1;
- }
- *zvec_n_bits = i;
-}
-
-#define _(TYPE,IS_SIGNED) \
- void zvec_decode_##TYPE (uword * zvec, \
- uword * zvec_n_bits, \
- uword coding, \
- void * data, \
- uword data_stride, \
- uword n_data) \
- { \
- return zvec_decode_inline (zvec, zvec_n_bits, \
- coding, \
- data, data_stride, n_data, \
- /* data_bytes */ sizeof (TYPE), \
- /* is_signed */ IS_SIGNED); \
- }
-
-_(u8, /* is_signed */ 0);
-_(u16, /* is_signed */ 0);
-_(u32, /* is_signed */ 0);
-_(u64, /* is_signed */ 0);
-_(i8, /* is_signed */ 1);
-_(i16, /* is_signed */ 1);
-_(i32, /* is_signed */ 1);
-_(i64, /* is_signed */ 1);
-
-#undef _
-
-/* Compute number of bits needed to encode given histogram. */
-static uword
-zvec_coding_bits (uword coding, uword * histogram_counts, uword min_bits)
-{
- uword n_type_bits, n_bits;
- uword this_count, last_count, max_count_index;
- uword i, b, l;
-
- n_bits = 0;
- n_type_bits = 1;
- last_count = 0;
- max_count_index = vec_len (histogram_counts) - 1;
-
- /* Coding is not large enough to encode given data. */
- if (coding <= max_count_index)
- return ~0;
-
- i = 0;
- while (coding != 0)
- {
- b = first_set (coding);
- l = min_log2 (b);
- i += b;
-
- this_count =
- histogram_counts[i > max_count_index ? max_count_index : i - 1];
-
- /* No more data to encode? */
- if (this_count == last_count)
- break;
-
- /* Last coding is i 0 ... 0 so we don't need an extra type bit. */
- if (coding == b)
- n_type_bits--;
-
- n_bits += (this_count - last_count) * (n_type_bits + l);
-
- /* This coding cannot be minimal: so return. */
- if (n_bits >= min_bits)
- return ~0;
-
- last_count = this_count;
- coding ^= b;
- n_type_bits++;
- }
-
- return n_bits;
-}
-
-uword
-_zvec_coding_from_histogram (void *histogram,
- uword histogram_len,
- uword histogram_elt_count_offset,
- uword histogram_elt_bytes,
- uword max_value_to_encode,
- zvec_coding_info_t * coding_return)
-{
- uword coding, min_coding;
- uword min_coding_bits, coding_bits;
- uword i, n_bits_set, total_count;
- uword *counts;
- zvec_histogram_count_t *h_count = histogram + histogram_elt_count_offset;
-
- if (histogram_len < 1)
- {
- coding_return->coding = 0;
- coding_return->min_coding_bits = 0;
- coding_return->n_data = 0;
- coding_return->n_codes = 0;
- coding_return->ave_coding_bits = 0;
- return 0;
- }
-
- total_count = 0;
- counts = vec_new (uword, histogram_len);
- for (i = 0; i < histogram_len; i++)
- {
- zvec_histogram_count_t this_count = h_count[0];
- total_count += this_count;
- counts[i] = total_count;
- h_count =
- (zvec_histogram_count_t *) ((void *) h_count + histogram_elt_bytes);
- }
-
- min_coding = 0;
- min_coding_bits = ~0;
-
- {
- uword base_coding =
- max_value_to_encode !=
- ~0 ? (1 + max_value_to_encode) : vec_len (counts);
- uword max_coding = max_pow2 (2 * base_coding);
-
- for (n_bits_set = 1; n_bits_set <= 8; n_bits_set++)
- {
- for (coding = pow2_mask (n_bits_set);
- coding < max_coding;
- coding = next_with_same_number_of_set_bits (coding))
- {
- coding_bits = zvec_coding_bits (coding, counts, min_coding_bits);
- if (coding_bits >= min_coding_bits)
- continue;
- min_coding_bits = coding_bits;
- min_coding = coding;
- }
- }
- }
-
- if (coding_return)
- {
- coding_return->coding = min_coding;
- coding_return->min_coding_bits = min_coding_bits;
- coding_return->n_data = total_count;
- coding_return->n_codes = vec_len (counts);
- coding_return->ave_coding_bits =
- (f64) min_coding_bits / (f64) total_count;
- }
-
- vec_free (counts);
-
- return min_coding;
-}
-
-u8 *
-format_zvec_coding (u8 * s, va_list * args)
-{
- zvec_coding_info_t *c = va_arg (*args, zvec_coding_info_t *);
- return format (s,
- "zvec coding 0x%x, %d elts, %d codes, %d bits total, %.4f ave bits/code",
- c->coding, c->n_data, c->n_codes, c->min_coding_bits,
- c->ave_coding_bits);
-}
-
-/*
- * fd.io coding-style-patch-verification: ON
- *
- * Local Variables:
- * eval: (c-set-style "gnu")
- * End:
- */