//***************************************************************************
// This source code is copyrighted 2002 by Google Inc.  All rights
// reserved.  You are given a limited license to use this source code for
// purposes of participating in the Google programming contest.  If you
// choose to use or distribute the source code for any other purpose, you
// must either (1) first obtain written approval from Google, or (2)
// prominently display the foregoing copyright notice and the following
// warranty and liability disclaimer on each copy used or distributed.
// 
// The source code and repository (the "Software") is provided "AS IS",
// with no warranty, express or implied, including but not limited to the
// implied warranties of merchantability and fitness for a particular
// use.  In no event shall Google Inc. be liable for any damages, direct
// or indirect, even if advised of the possibility of such damages.
//***************************************************************************

//
// Raw support for varint encoding.  Higher level interfaces are
// provided by Encoder/Decoder.  Clients should typically use
// those interfaces, unless speed is paramount.
//
// Provided routines:
//      vi_parse32_unchecked
//      vi_parse64_unchecked
//      vi_encode32_unchecked
//      vi_encode64_unchecked

#ifndef _VARINT_H
#define _VARINT_H

#include "goo-basictypes.h"

// Just a namespace, not a real class
class Varint {
 public:
  // Maximum lengths of varint encoding of uint32 and uint64
  static const int kMax32 = 5;
  static const int kMax64 = 10;

  // REQUIRES   "ptr" points to a buffer of length at least kVarintMaxXX
  // EFFECTS    Scan next varint from "ptr" and store in OUTPUT.
  //            Returns pointer just past last read byte.  Returns
  //            NULL if a valid varint value was not found.
  static const char* Parse32(const char* ptr, uint32* OUTPUT);
  static const char* Parse64(const char* ptr, uint64* OUTPUT);

  // REQUIRES   "ptr" points to a buffer of length sufficient to hold "v".
  // EFFECTS    Encodes "v" into "ptr" and returns a pointer to the
  //            byte just past the last encoded byte.
  static char* Encode32(char* ptr, uint32 v);
  static char* Encode64(char* ptr, uint64 v);

  // EFFECTS    Returns the encoding length of the specified value.
  static int Length32(uint32 v);
  static int Length64(uint64 v);
};

/***** Implementation details; clients should ignore *****/
  
inline const char* Varint::Parse32(const char* ptr, uint32* OUTPUT) {
  // Fast path
  uint32 byte, result;
  byte = *(ptr++); result = byte & 127;          if (byte < 128) goto done;
  byte = *(ptr++); result |= (byte & 127) <<  7; if (byte < 128) goto done;
  byte = *(ptr++); result |= (byte & 127) << 14; if (byte < 128) goto done;
  byte = *(ptr++); result |= (byte & 127) << 21; if (byte < 128) goto done;
  byte = *(ptr++); result |= (byte & 127) << 28; if (byte < 128) goto done;
  return NULL;       // Value is too long to be a varint32
 done:
  *OUTPUT = result;
  return ptr;
}

inline const char* Varint::Parse64(const char* ptr, uint64* OUTPUT) {
  // Fast path: need to accumulate data in upto three result fragments
  //    res1    bits 0..27
  //    res2    bits 28..55
  //    res3    bits 56..63
  uint32 byte, res1, res2=0, res3=0;
  
  byte = *(ptr++); res1 = byte & 127;          if (byte < 128) goto done;
  byte = *(ptr++); res1 |= (byte & 127) <<  7; if (byte < 128) goto done;
  byte = *(ptr++); res1 |= (byte & 127) << 14; if (byte < 128) goto done;
  byte = *(ptr++); res1 |= (byte & 127) << 21; if (byte < 128) goto done;
  
  byte = *(ptr++); res2 = byte & 127;          if (byte < 128) goto done;
  byte = *(ptr++); res2 |= (byte & 127) <<  7; if (byte < 128) goto done;
  byte = *(ptr++); res2 |= (byte & 127) << 14; if (byte < 128) goto done;
  byte = *(ptr++); res2 |= (byte & 127) << 21; if (byte < 128) goto done;
  
  byte = *(ptr++); res3 = byte & 127;          if (byte < 128) goto done;
  byte = *(ptr++); res3 |= (byte & 127) <<  7; if (byte < 128) goto done;
  
  return NULL;       // Value is too long to be a varint64
  
 done:
  *OUTPUT = res1 | (uint64(res2) << 28) | (uint64(res3) << 56);
  return ptr;
}

inline int Varint::Length32(uint32 v) {
  // Each byte of output stores 7 bits of "v" until "v" becomes zero
  int nbytes = 0;
  do {
    nbytes++;
    v >>= 7;
  } while (v != 0);
  return nbytes;
}

inline int Varint::Length64(uint64 v) {
  // Each byte of output stores 7 bits of "v" until "v" becomes zero
  int nbytes = 0;
  do {
    nbytes++;
    v >>= 7;
  } while (v != 0);
  return nbytes;
}

#endif /* _VARINT_H */