src/utils/bitstring/bitstring_c.c

   1 /*
   2  * Bitstring library.
   3  *
   4  * Copyright (C) 2008-2016 Red Hat Inc., Richard W.M. Jones
   5  * Copyright (C) 2016 Red Hat Inc, Richard W.M. Jones, Xavier R. Guerin.
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2 of the License, or (at your option) any later version,
  11  * with the OCaml linking exception described in COPYING.LIB.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 /* This file contains hand-coded, optimized C implementations of
  24  * certain very frequently used functions.
  25  */
  26
  27 #if defined(__APPLE__)
  28 #include <machine/endian.h>
  29 #elif defined(__FreeBSD__)
  30 #include <sys/endian.h>
  31 #elif defined(__MINGW32__)
  32 #include <sys/param.h>
  33 #elif defined(_WIN32) && defined(_MSC_VER) && (defined(_M_X64) || defined (_M_IX86))
  34 #define BIG_ENDIAN      4321
  35 #define LITTLE_ENDIAN   1234
  36 #define BYTE_ORDER      LITTLE_ENDIAN
  37 #else
  38 #include <endian.h>
  39 #endif
  40
  41 #include <stdio.h>
  42 #include <stdlib.h>
  43 #include <stdint.h>
  44 #if defined(HAVE_BYTESWAP_H)
  45 #  include <byteswap.h>
  46 #else
  47 #  include "byteswap.h"
  48 #endif
  49
  50 #include <string.h>
  51
  52 #include <caml/mlvalues.h>
  53 #include <caml/fail.h>
  54 #include <caml/memory.h>
  55 #include <caml/alloc.h>
  56
  57 /*
  58  * Prefix fastpath functions.
  59  */
  60
  61 static char prefix_mask_lookup[8] = {
  62   0x00, 0x80, 0xC0, 0xE0,
  63   0xF0, 0xF8, 0xFC, 0xFE
  64 };
  65
  66 static
  67 int match_partial_left(int len, char source, char prefix)
  68 {
  69   register char mask = ~prefix_mask_lookup[len];
  70   return (source & mask) == (prefix & mask);
  71 }
  72
  73 static
  74 int match_partial_right(int len, char source, char prefix)
  75 {
  76   register char mask = prefix_mask_lookup[len];
  77   return (source & mask) == (prefix & mask);
  78 }
  79
  80 CAMLprim value
  81 ocaml_bitstring_is_prefix_fastpath(value b1, value o1, value b2, value o2, value l2)
  82 {
  83   CAMLparam5 (b1, o1, b2, o2, l2);
  84   int il2 = Int_val(l2);
  85   /*
  86    * Find the beginning of the bitstrings.
  87    */
  88   int bo1 = Int_val(o1) >> 3;
  89   int bo2 = Int_val(o2) >> 3;
  90   char * ptr1 = &((char *)String_val(b1))[bo1];
  91   char * ptr2 = &((char *)String_val(b2))[bo2];
  92   /*
  93    * Compute the left partial match if the offset mod 8 != 0.
  94    */
  95   int sh = Int_val(o2) & 0x7;
  96   if (sh != 0) {
  97     if (!match_partial_left(sh, *ptr1, *ptr2)) {
  98       CAMLreturn (Val_false);
  99     }
 100     il2 -= 8 - sh;
 101     ptr1++, ptr2++;
 102   }
 103   /*
 104    * Check the part of the prefix that fits in bytes using memcmp.
 105    */
 106   int bl2 = il2 >> 3;
 107   if (memcmp(ptr1, ptr2, bl2) != 0) {
 108     CAMLreturn (Val_false);
 109   }
 110   /*
 111    * Check the remainder of the prefix if there is any.
 112    */
 113   int rem = il2 & 0x7;
 114   if (rem) {
 115     int res = match_partial_right(rem, ptr1[bl2], ptr2[bl2]);
 116     CAMLreturn (Val_bool(res));
 117   }
 118   /*
 119    * The prefix exists.
 120    */
 121   CAMLreturn (Val_true);
 122 }
 123
 124 /*
 125  * Extract fastpath functions.
 126  *
 127  * These are used in the common case for reading ints where the following
 128  * conditions are known to be true:
 129  * (a) the int size is a whole number of bytes (eg. 16, 24, 32, etc bits)
 130  * (b) the access in the match is byte-aligned
 131  * (c) the access in the underlying bitstring is byte-aligned
 132  *
 133  * These functions used to all be "noalloc" meaning they must not perform any
 134  * OCaml allocations.  However starting with OCaml 4.02, a compiler optimization
 135  * means that unforunately we now have to use ordinary alloc functions in some
 136  * cases.
 137  *
 138  * The final offset in the string is calculated by the OCaml (caller) code. All
 139  * we need to do is to read the string+offset and byteswap, sign-extend as
 140  * necessary.
 141  *
 142  * There is one function for every combination of:
 143  * (i) int size: 16, 32, 64 bits
 144  * (ii) endian: bigendian, littleendian, nativeendian
 145  * (iii) signed and unsigned
 146  *
 147  * XXX Future work: Expand this to 24, 40, 48, 56 bits.  This
 148  * requires some extra work because sign-extension won't "just happen".
 149  */
 150
 151 #if BYTE_ORDER == BIG_ENDIAN
 152 #define swap_be(size,v)
 153 #define swap_le(size,v) v = bswap_##size (v)
 154 #define swap_ne(size,v)
 155 #else
 156 #define swap_be(size,v) v = bswap_##size (v)
 157 #define swap_le(size,v)
 158 #define swap_ne(size,v)
 159 #endif
 160
 161 #define extract_fastpath_zero_copy(size, endian, sign, type)      \
 162   CAMLprim value                                                  \
 163   ocaml_bitstring_extract_fastpath_int##size##_##endian##_##sign  \
 164   (value strv, value offv)                                        \
 165 {                                                                 \
 166   CAMLparam2 (strv, offv);                                        \
 167   type *ptr = (type *)((char *)String_val(strv) + Int_val(offv)); \
 168   type r;                                                         \
 169   memcpy(&r, ptr, sizeof(r));                                     \
 170   swap_##endian(size,r);                                          \
 171   CAMLreturn (Val_int(r));                                        \
 172 }
 173
 174 #define extract_fastpath_with_copy(size, endian, sign, type)      \
 175   CAMLprim value                                                  \
 176   ocaml_bitstring_extract_fastpath_int##size##_##endian##_##sign  \
 177   (value strv, value offv)                                        \
 178 {                                                                 \
 179   CAMLparam2 (strv, offv);                                        \
 180   CAMLlocal1 (rv);                                                \
 181   type *ptr = (type *)((char *)String_val(strv) + Int_val(offv)); \
 182   type r;                                                         \
 183   memcpy(&r, ptr, sizeof(r));                                     \
 184   swap_##endian(size,r);                                          \
 185   rv = caml_copy_int##size(r);                                    \
 186   CAMLreturn(rv);                                                 \
 187 }
 188
 189 extract_fastpath_zero_copy(16, be, unsigned, uint16_t)
 190 extract_fastpath_zero_copy(16, le, unsigned, uint16_t)
 191 extract_fastpath_zero_copy(16, ne, unsigned, uint16_t)
 192 extract_fastpath_zero_copy(16, be, signed  , int16_t )
 193 extract_fastpath_zero_copy(16, le, signed  , int16_t )
 194 extract_fastpath_zero_copy(16, ne, signed  , int16_t )
 195
 196 extract_fastpath_with_copy(32, be, unsigned, uint32_t)
 197 extract_fastpath_with_copy(32, le, unsigned, uint32_t)
 198 extract_fastpath_with_copy(32, ne, unsigned, uint32_t)
 199 extract_fastpath_with_copy(32, be, signed  , int32_t )
 200 extract_fastpath_with_copy(32, le, signed  , int32_t )
 201 extract_fastpath_with_copy(32, ne, signed  , int32_t )
 202
 203 extract_fastpath_with_copy(64, be, unsigned, uint64_t)
 204 extract_fastpath_with_copy(64, le, unsigned, uint64_t)
 205 extract_fastpath_with_copy(64, ne, unsigned, uint64_t)
 206 extract_fastpath_with_copy(64, be, signed  , int64_t )
 207 extract_fastpath_with_copy(64, le, signed  , int64_t )
 208 extract_fastpath_with_copy(64, ne, signed  , int64_t )
 209
 210 // vim: ts=2:sts=2:sw=2:et