blokutil.cpp

伯克利做的SFTP安全文件传输协议

// blokutil.cc
// code for blokutil.h
// copyright SafeTP Development Group, Inc., 2000  Terms of use are as specified in license.txt

#include "blokutil.h"      // this module
#include "rng.h"           // LC_RNG
#include "exc.h"           // xFormat
#include <string.h>        // strlen


// --------------- functional constructors -----------------
DataBlock Left(int bytes, DataBlock const &block)
{
  checkFormat(bytes >= 0 &&
              bytes <= block.getDataLen(), "Block is too small");
  DataBlock ret(block);
  ret.setDataLen(bytes);
  return ret;
}

DataBlock concat(DataBlock const &b1, DataBlock const &b2)
{
  DataBlock ret(b1.getDataLen() + b2.getDataLen());
  memcpy(ret.getData(), b1.getDataC(), b1.getDataLen());
  memcpy(ret.getData() + b1.getDataLen(), b2.getDataC(),
         b2.getDataLen());
  ret.setDataLen(b1.getDataLen() + b2.getDataLen());
  return ret;
}

DataBlock Right(int bytes, DataBlock const &src)
{
  checkFormat(bytes >= 0 &&
              bytes <= src.getDataLen(), "Block is too small");
  DataBlock ret(bytes);
  memcpy(ret.getData(), src.getDataC() + src.getDataLen() - bytes, bytes);
  ret.setDataLen(bytes);
  return ret;
}


DataBlock randomDataBlock(RandomNumberGenerator &rng, int bytes)
{
  DataBlock ret(bytes);
  rng.GetBlock(ret.getData(), bytes);
  ret.setDataLen(bytes);
  return ret;
}



// ------------- Integer / DataBlock conversions --------------
Integer dataBlock2Integer(DataBlock const &block)
{
  // straightforward conversion from base-256
  Integer ret(0);
  for (int i=0; i<block.getDataLen(); i++) {
    ret <<= 8;
    ret += (unsigned)(block.getDataC()[i]);
  }

  return ret;
}


DataBlock integer2DataBlock(Integer const &value)
{
  int sz = sizeAsDataBlock(value);
  return integer2DataBlock(value, sz);
}

DataBlock integer2DataBlock(Integer const &value, int sz)
{
  xassert(value >= 0);
  xassert(sz >= sizeAsDataBlock(value));
  DataBlock ret(sz);

  // convert to base-256, working from lsb to msb
  Integer temp(value);
  for (int i=sz-1; i>=0; i--) {
    ret.getData()[i] = temp.leastSigByte();
    temp >>= 8;
  }

  ret.setDataLen(sz);
  return ret;
}


int sizeAsDataBlock(Integer const &value)
{
  xassert(value >= 0);

  if (value == 0) {
    return 1;     // encoded as [ 0x00 ]
  }

  int n = (value.numBits()-1)/8;
    // e.g., if value is 255, n is 0
    //       if value is 256, n is 1

  return n+1;
    // e.g., 255 is encoded as [ 0xff ]
    //       256 is encoded as [ 0x01 0x00 ]
}


// -------------- DataBlock as stream -----------------------
void appendBlock(DataBlock &stream, DataBlock const &block)
{
  stream.growDataLen(block.getDataLen());
  memcpy(stream.getData() + stream.getDataLen() - block.getDataLen(),
         block.getDataC(),
         block.getDataLen());
}

DataBlock removeBlock(DataBlock &block, int bytes)
{
  DataBlock ret = Right(bytes, block);
    // Right() implicitly checks formatting

  block.changeDataLen(-bytes);
  return ret;
}


void appendNBO32(DataBlock &data, long value)
{
  data.growDataLen(+4);

  byte *p = data.getData() + data.getDataLen() - 4;
  for (int i=0; i<4; i++) {
    int shamt = 24 - i*8;
    p[i] = (byte)((value >> shamt) & 0xff);
  }
}


// todo: why does this fn sign-extend its result?
long removeNBO32(DataBlock &data)
{
  checkFormat(data.getDataLen() >= 4,
              "Block is too small to contain a 32-bit integer.");
  data.growDataLen(-4);

  long value = 0;
  byte const *p = data.getData() + data.getDataLen();
  for (int i=0; i<4; i++) {
    int shamt = 24 - i*8;
    value |= p[i] << shamt;
  }

  // sign-extend
  if (value & 0x80000000) {
    for (int i=4; i<(int)sizeof(value); i++) {
      value |= 0xff << (i * 8);
    }
  }

  return value;
}


enum { ENCODED_SIGN_BIT = 0x80000000 };

void appendInteger(DataBlock &stream, Integer const &value)
{
  // not hugely efficient...
  DataBlock iblock = integer2DataBlock(abs(value));
  appendBlock(stream, iblock);

  long blocklen = iblock.getDataLen();
  if (value < 0) {
    blocklen |= ENCODED_SIGN_BIT;
  }
  appendNBO32(stream, blocklen);
}

Integer removeInteger(DataBlock &stream)
{
  long len = removeNBO32(stream);
  bool negative = !!( len & ENCODED_SIGN_BIT );

  // turn off sign bit in length, if it's on
  len &= ~ENCODED_SIGN_BIT;

  Integer ret = dataBlock2Integer(removeBlock(stream, len));
  if (negative) {
    ret *= -1;
  }

  return ret;
}


void appendString(DataBlock &stream, char const *str)
{
  int len = strlen(str);
  stream.ensureAtLeast(stream.getDataLen() + len + 4);
    // string (no null) + length

  // append string
  memcpy(stream.getData() + stream.getDataLen(),
         str, len);
  stream.growDataLen(len);

  // append string length
  appendNBO32(stream, len);
}

string removeString(DataBlock &stream)
{
  // get length
  int len = removeNBO32(stream);
  checkFormat(len >= 0 &&
              len <= stream.getDataLen(), "Encoded string length is invalid");

  // remove string
  string ret(len+1);
  stream.growDataLen(-len);
  memcpy(ret.pchar(),
         stream.getData() + stream.getDataLen(),
         len);
  ret[len] = 0;    // null terminator

  return ret;
}


void appendByte(DataBlock &stream, byte b)
{
  stream.growDataLen(+1);
  stream.getData()[ stream.getDataLen()-1 ] = b;
}

byte removeByte(DataBlock &stream)
{
  checkFormat(stream.getDataLen() >= 1,
              "Block does not contain a byte.");

  byte b = stream.getDataC()[ stream.getDataLen()-1 ];
  stream.growDataLen(-1);

  return b;
}


void appendIPAddress(DataBlock &stream, IPAddress addr)
{
  // format:
  //   [ 10 bytes of 0 ][ 0xFFFF ][ network byte order addr ]
  loopi(10) {
    appendByte(stream, 0);
  }
  appendByte(stream, 0xFF);
  appendByte(stream, 0xFF);

  appendNBO32(stream, addr);
}

IPAddress removeIPAddress(DataBlock &stream)
{
  IPAddress ret = (IPAddress)removeNBO32(stream);

  bool ok = true;
  ok = (removeByte(stream) == 0xFF) && ok;
  ok = (removeByte(stream) == 0xFF) && ok;
  loopi(10) {
    ok = (removeByte(stream) == 0) && ok;
  }
  checkFormat(ok, "First 12 bytes of IP address fail to conform to "
                  "format for \"IPv4-mapped IPv6 address\" as specified "
                  "by RFC 2373.");

  return ret;
}


// ---------------- test code -----------------
#ifdef TEST_BLOKUTIL

#include "test.h"      // test utils


// bit of a hack, but no big deal for testing
//ostream& operator<< (ostream &os, DataBlock const &block)
//{
//  return os << block.getDataC();
//}


template <class T>
bool testIdentity(
  void (*append)(DataBlock &stream, T const &value),
  T (*remove)(DataBlock &stream),
  T const &value)
{
  DataBlock stream("a");
  append(stream, value);
  if (remove(stream) != value) {
    cout << "test failed for " << value << endl;
    return false;
  }
  else {
    return true;
  }
}


// wrapper to get syntax just right
#define MAKE_TESTFUNC(type, type_name)                              \
void test_append##type_name(DataBlock &stream, type const &value)   \
{                                                                   \
  append##type_name(stream, value);                                 \
}

MAKE_TESTFUNC(long, NBO32)
MAKE_TESTFUNC(string, String)
MAKE_TESTFUNC(byte, Byte)
MAKE_TESTFUNC(IPAddress, IPAddress)


void entry()
{
  bool ok = true;

  // test NBO32 longs, small Integers, IP addresses
  {
    static const long vals[] = {
      0, 1, 2, 3, -1, -2, 0xffff, 0x10000,
      0x7ffffffe, 0x7fffffff, -0x80000000,
      -0x7fffffff, -0x7ffffffe,
      (136 << 24) | (152 << 16) | (99 << 8) | 6,
    };
    loopi(TABLESIZE(vals)) {
      ok = testIdentity(test_appendNBO32, removeNBO32, vals[i]) && ok;
      ok = testIdentity(appendInteger, removeInteger, Integer(vals[i])) && ok;
      ok = testIdentity(test_appendIPAddress, removeIPAddress,
                        (IPAddress)vals[i]) && ok;
    }
  }

  // test large Integers
  {
#   define I(str) Integer(str, 10)
    static const Integer vals[] = {
      I("123456789012345678901234567890"),
      I("123456789012345678901234567890"
        "123456789012345678901234567890"
        "123456789012345678901234567890"
        "123456789012345678901234567890"
        "123456789012345678901234567890"),
      I("-123456789012345678901234567890"
         "123456789012345678901234567890"
         "123456789012345678901234567890"
         "123456789012345678901234567890"
         "123456789012345678901234567890")
    };
#   undef I
    loopi(TABLESIZE(vals)) {
      ok = testIdentity(appendInteger, removeInteger, vals[i]) && ok;
    }
  }

  // some strings
  {
    static const string vals[] = {
      string("yadda smacker"),
      string(""),
      string("some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars "
             "some long thing that will be longer than 255 chars ")
    };
    cout << "strings: ";
    loopi(TABLESIZE(vals)) {
      ok = testIdentity(test_appendString, removeString, vals[i]) && ok;
      cout << ".";
    }
    cout << endl;
  }


  // bytes
  {
    static const byte vals[] = {
      'a', 'b', 'c', 0xff, 0, 1, 2
    };
    loopi(TABLESIZE(vals)) {
      ok = testIdentity(test_appendByte, removeByte, vals[i]) && ok;
    }
  }


  // random block
  {
    LC_RNG rng(1);
    randomDataBlock(rng, 10).print("random block");
  }


  // integer encodings
  {
    static struct {
      char const *decimal;
      byte binary[10];
      int binaryLen;
    } const arr[] = {
      { "0", { 0x00 }, 1 },
      { "1", { 0x01 }, 1 },
      { "2", { 0x02 }, 1 },
      { "255", { 0xff }, 1 },
      { "256", { 0x01, 0x00 }, 2 },
      { "257", { 0x01, 0x01 }, 2 },
      { "258", { 0x01, 0x02 }, 2 },
      { "65535", { 0xff, 0xff }, 2 },
      { "65536", { 0x01, 0x00, 0x00 }, 3 },
      { "65537", { 0x01, 0x00, 0x01 }, 3 },
      { "65538", { 0x01, 0x00, 0x02 }, 3 },
    };

    loopi(TABLESIZE(arr)) {
      Integer val(arr[i].decimal, 10);
      DataBlock block(arr[i].binary, arr[i].binaryLen);

      xassert(val == dataBlock2Integer(block));
      {
        DataBlock blk = integer2DataBlock(val);
        if (blk != block) {
          cout << "integer2DataBlock failed for " << arr[i].decimal << ":\n";
          block.print("should be");
          blk.print("got instead");
        }
        xassert(block == blk);
      }
      xassert(sizeAsDataBlock(val) == arr[i].binaryLen);
    }
  }


  if (ok) {
    cout << "all tests passed\n";
  }
  else {
    cout << "at least one test failed\n";
  }
}


USUAL_MAIN

#endif // TEST_BLOKUTIL