Number.h

Go to the documentation of this file.

#ifndef OSMSCOUT_NUMBER_H
#define OSMSCOUT_NUMBER_H

/*
  This source is part of the libosmscout library
  Copyright (C) 2009  Tim Teulings

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
*/

#include <osmscout/CoreImportExport.h>

#include <array>
#include <limits>
#include <cstddef>
#include <cassert>

#include <osmscout/system/SystemTypes.h>

namespace osmscout {

  template<typename N>
  inline unsigned int EncodeNumberSigned(N number,
                                         char* buffer)
  {
    unsigned int bytes=1;
    char         val;

    if (number<0) {
      number^=static_cast<N>(-1);
      val=static_cast<char>((number & 0x3f) << 1 | 0x01);
    }
    else {
      val=static_cast<char>((number & 0x3f) << 1);
    }

    number>>=6;

    while (number!=0) {
      *(buffer++)=val | 0x80;
      val=static_cast<char>(number & 0x7f);
      number>>=7;
      bytes++;
    }

    *buffer=val;
    return bytes;
  }

  template<typename N>
  inline unsigned int EncodeNumberUnsigned(N number,
                                           char* buffer)
  {
    unsigned int bytes=0;

    while (number>0x7f) {
      buffer[bytes]=static_cast<char>((number & 0x7f) | 0x80);
      number>>=7;
      bytes++;
    }

    buffer[bytes]=static_cast<char>(number);
    bytes++;

    return bytes;
  }

  template<bool is_signed, typename N>
  struct EncodeNumberTemplated
  {
  };

  template<typename N>
  struct EncodeNumberTemplated<true, N>
  {
    static inline unsigned int f(N number,char* buffer)
    {
      return EncodeNumberSigned<N>(number,buffer);
    }
  };

  template<typename N>
  struct EncodeNumberTemplated<false, N>
  {
    static inline unsigned int f(N number,char* buffer)
    {
      return EncodeNumberUnsigned<N>(number,buffer);
    }
  };

  template<typename N>
  inline unsigned int EncodeNumber(N number,
                                   char* buffer)
  {
    return EncodeNumberTemplated<std::numeric_limits<N>::is_signed, N>
      ::f(number,buffer);
  }

  template<typename N, size_t S>
  inline unsigned int EncodeNumber(N number,
                                   std::array<char, S> &buffer)
  {
    if constexpr (std::numeric_limits<N>::is_signed) {
      static_assert(sizeof(N) * 64 + 7 <= S * 56, "Not enough big buffer for encoding signed number");
    } else {
      static_assert(sizeof(N) * 64 <= S * 56, "Not enough big buffer for encoding unsigned number");
    }
    auto dataWritten = EncodeNumberTemplated<std::numeric_limits<N>::is_signed, N>
      ::f(number,buffer.data());
    assert(dataWritten<=S);
    return dataWritten;
  }

  template<typename N>
  inline unsigned int DecodeNumberSigned(const char* buffer,
                                         N& number)
  {
    unsigned int shift=0;
    unsigned int nextShift=0;
    unsigned int bytes=1;

    // negative form
    if ((*buffer & 0x01)!=0) {
      N val=(*buffer & 0x7e) >> 1;

      number=-1;
      nextShift=6;

      while ((*(buffer++) & 0x80)!=0) {
        number^=(val << shift);
        val=*buffer & 0x7f;
        shift=nextShift;
        nextShift+=7;
        bytes++;
      }

      number^=static_cast<N>(val) << shift;
    }
    else {
      N val=(*buffer & 0x7e) >> 1;

      number=0;
      nextShift=6;

      while ((*(buffer++) & 0x80)!=0) {
        number|=(val << shift);
        val=*buffer & 0x7f;
        shift=nextShift;
        nextShift+=7;
        bytes++;
      }

      number|=static_cast<N>(val) << shift;
    }

    return bytes;
  }

  template<typename N>
  inline unsigned int DecodeNumberUnsigned(const char* buffer,
                                           N& number)
  {
    unsigned int shift=0;
    unsigned int bytes=1;

    number=0;

    while (true) {
      number|=static_cast<N>(*buffer & 0x7f) << shift;

      if (((*buffer) & 0x80)==0) {
        return bytes;
      }

      bytes++;
      buffer++;
      shift+=7;
    }

    // Only for the compiler...
    return bytes;
  }

  template<bool is_signed, typename N>
  struct DecodeNumberTemplated
  {
  };

  template<typename N>
  struct DecodeNumberTemplated<true, N>
  {
    static inline unsigned int f(const char* buffer, N& number)
    {
      return DecodeNumberSigned<N>(buffer,number);
    }
  };

  template<typename N>
  struct DecodeNumberTemplated<false, N>
  {
    static inline unsigned int f(const char* buffer, N& number)
    {
      return DecodeNumberUnsigned<N>(buffer,number);
    }
  };

  template<typename N>
  inline unsigned int DecodeNumber(const char* buffer,
                                   N& number)
  {
    return DecodeNumberTemplated<std::numeric_limits<N>::is_signed, N>
      ::f(buffer,number);
  }

  template<typename N>
  inline N BitsToBytes(N bits)
  {
    return bits%8==0 ? bits/8 : bits/8+1;
  }

  template<typename N>
  uint8_t BytesNeededToEncodeNumber(N number)
  {
    uint8_t bytes=0;

    while (number!=0) {
      number=number/256;
      bytes++;
    }

    if (bytes==0) {
      bytes=1;
    }

    return bytes;
  }

  template<typename N>
  uint8_t BitsNeededToEncodeNumber(N number)
  {
    uint8_t bits=0;

    while (number!=0) {
      number=number/2;
      bits++;
    }

    if (bits==0) {
      bits=1;
    }

    return bits;
  }

  extern OSMSCOUT_API uint64_t InterleaveNumbers(uint32_t a,
                                                 uint32_t b);
}

#endif