be/src/kudu/util/memcmpable_varint.cc

// Licensed to the Apache Software Foundation (ASF) under one
// or more contributor license agreements.  See the NOTICE file
// distributed with this work for additional information
// regarding copyright ownership.  The ASF licenses this file
// to you 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.
//
// This file contains code derived from sqlite4, distributed in the public domain.
//
// A variable length integer is an encoding of 64-bit unsigned integers
// into between 1 and 9 bytes.  The encoding is designed so that small
// (and common) values take much less space that larger values.  Additional
// properties:
//
//    *  The length of the varint can be determined after examining just
//       the first byte of the encoding.
//
//    *  Varints compare in numerical order using memcmp().
//
//************************************************************************
//
// Treat each byte of the encoding as an unsigned integer between 0 and 255.
// Let the bytes of the encoding be called A0, A1, A2, ..., A8.
//
// DECODE
//
// If A0 is between 0 and 240 inclusive, then the result is the value of A0.
//
// If A0 is between 241 and 248 inclusive, then the result is
// 240+256*(A0-241)+A1.
//
// If A0 is 249 then the result is 2288+256*A1+A2.
//
// If A0 is 250 then the result is A1..A3 as a 3-byte big-ending integer.
//
// If A0 is 251 then the result is A1..A4 as a 4-byte big-ending integer.
//
// If A0 is 252 then the result is A1..A5 as a 5-byte big-ending integer.
//
// If A0 is 253 then the result is A1..A6 as a 6-byte big-ending integer.
//
// If A0 is 254 then the result is A1..A7 as a 7-byte big-ending integer.
//
// If A0 is 255 then the result is A1..A8 as a 8-byte big-ending integer.
//
// ENCODE
//
// Let the input value be V.
//
// If V<=240 then output a single by A0 equal to V.
//
// If V<=2287 then output A0 as (V-240)/256 + 241 and A1 as (V-240)%256.
//
// If V<=67823 then output A0 as 249, A1 as (V-2288)/256, and A2
// as (V-2288)%256.
//
// If V<=16777215 then output A0 as 250 and A1 through A3 as a big-endian
// 3-byte integer.
//
// If V<=4294967295 then output A0 as 251 and A1..A4 as a big-ending
// 4-byte integer.
//
// If V<=1099511627775 then output A0 as 252 and A1..A5 as a big-ending
// 5-byte integer.
//
// If V<=281474976710655 then output A0 as 253 and A1..A6 as a big-ending
// 6-byte integer.
//
// If V<=72057594037927935 then output A0 as 254 and A1..A7 as a
// big-ending 7-byte integer.
//
// Otherwise then output A0 as 255 and A1..A8 as a big-ending 8-byte integer.
//
// SUMMARY
//
//    Bytes    Max Value    Digits
//    -------  ---------    ---------
//      1      240           2.3
//      2      2287          3.3
//      3      67823         4.8
//      4      2**24-1       7.2
//      5      2**32-1       9.6
//      6      2**40-1      12.0
//      7      2**48-1      14.4
//      8      2**56-1      16.8
//      9      2**64-1      19.2

#include <cstddef>

#include <glog/logging.h>

#include "kudu/util/faststring.h"
#include "kudu/util/memcmpable_varint.h"
#include "kudu/util/slice.h"

namespace kudu {

////////////////////////////////////////////////////////////
// Begin code ripped from sqlite4
////////////////////////////////////////////////////////////

// This function is borrowed from sqlite4/varint.c
static void varintWrite32(uint8_t *z, uint32_t y) {
  z[0] = (uint8_t)(y>>24);
  z[1] = (uint8_t)(y>>16);
  z[2] = (uint8_t)(y>>8);
  z[3] = (uint8_t)(y);
}


// Write a varint into z[].  The buffer z[] must be at least 9 characters
// long to accommodate the largest possible varint.  Return the number of
// bytes of z[] used.
//
// This function is borrowed from sqlite4/varint.c
static size_t sqlite4PutVarint64(uint8_t *z, uint64_t x) {
  uint64_t w, y;
  if (x <= 240) {
    z[0] = (uint8_t)x;
    return 1;
  }
  if (x <= 2287) {
    y = (uint64_t)(x - 240);
    z[0] = (uint8_t)(y/256 + 241);
    z[1] = (uint8_t)(y%256);
    return 2;
  }
  if (x <= 67823) {
    y = (uint64_t)(x - 2288);
    z[0] = 249;
    z[1] = (uint8_t)(y/256);
    z[2] = (uint8_t)(y%256);
    return 3;
  }
  y = (uint64_t)x;
  w = (uint64_t)(x>>32);
  if (w == 0) {
    if (y <= 16777215) {
      z[0] = 250;
      z[1] = (uint8_t)(y>>16);
      z[2] = (uint8_t)(y>>8);
      z[3] = (uint8_t)(y);
      return 4;
    }
    z[0] = 251;
    varintWrite32(z+1, y);
    return 5;
  }
  if (w <= 255) {
    z[0] = 252;
    z[1] = (uint8_t)w;
    varintWrite32(z+2, y);
    return 6;
  }
  if (w <= 65535) {
    z[0] = 253;
    z[1] = (uint8_t)(w>>8);
    z[2] = (uint8_t)w;
    varintWrite32(z+3, y);
    return 7;
  }
  if (w <= 16777215) {
    z[0] = 254;
    z[1] = (uint8_t)(w>>16);
    z[2] = (uint8_t)(w>>8);
    z[3] = (uint8_t)w;
    varintWrite32(z+4, y);
    return 8;
  }
  z[0] = 255;
  varintWrite32(z+1, w);
  varintWrite32(z+5, y);
  return 9;
}

// Decode the varint in the first n bytes z[].  Write the integer value
// into *pResult and return the number of bytes in the varint.
//
// If the decode fails because there are not enough bytes in z[] then
// return 0;
//
// Borrowed from sqlite4 varint.c
static int sqlite4GetVarint64(
  const uint8_t *z,
  int n,
  uint64_t *p_result) {
  unsigned int x;
  if ( n < 1) return 0;
  if (z[0] <= 240) {
    *p_result = z[0];
    return 1;
  }
  if (z[0] <= 248) {
    if ( n < 2) return 0;
    *p_result = (z[0]-241)*256 + z[1] + 240;
    return 2;
  }
  if (n < z[0]-246 ) return 0;
  if (z[0] == 249) {
    *p_result = 2288 + 256*z[1] + z[2];
    return 3;
  }
  if (z[0] == 250) {
    *p_result = (z[1]<<16) + (z[2]<<8) + z[3];
    return 4;
  }
  x = (z[1]<<24) + (z[2]<<16) + (z[3]<<8) + z[4];
  if (z[0] == 251) {
    *p_result = x;
    return 5;
  }
  if (z[0] == 252) {
    *p_result = (((uint64_t)x)<<8) + z[5];
    return 6;
  }
  if (z[0] == 253) {
    *p_result = (((uint64_t)x)<<16) + (z[5]<<8) + z[6];
    return 7;
  }
  if (z[0] == 254) {
    *p_result = (((uint64_t)x)<<24) + (z[5]<<16) + (z[6]<<8) + z[7];
    return 8;
  }
  *p_result = (((uint64_t)x)<<32) +
               (0xffffffff & ((z[5]<<24) + (z[6]<<16) + (z[7]<<8) + z[8]));
  return 9;
}

////////////////////////////////////////////////////////////
// End code ripped from sqlite4
////////////////////////////////////////////////////////////

void PutMemcmpableVarint64(faststring *dst, uint64_t value) {
  uint8_t buf[9];
  int used = sqlite4PutVarint64(buf, value);
  DCHECK_LE(used, sizeof(buf));
  dst->append(buf, used);
}

bool GetMemcmpableVarint64(Slice *input, uint64_t *value) {
  size_t size = sqlite4GetVarint64(input->data(), input->size(), value);
  input->remove_prefix(size);
  return size > 0;
}


} // namespace kudu