generic/rrdata.cpp

   1 #include "rrdata.hpp"
   2 #include <set>
   3 #include <cstring>
   4 #include <string>
   5 #include <iostream>
   6 #include <fstream>
   7 #include <sstream>
   8 #include "misc.hpp"
   9
  10 //
  11 // XABCDEFXXXXXXXXX
  12 // 0123456789XXXXXX
  13 //
  14 // ABCDEF0123456789XXXXXX
  15
  16 rrdata::instance::instance() throw(std::bad_alloc)
  17 {
  18         std::string rnd = get_random_hexstring(2 * RRDATA_BYTES);
  19         memset(bytes, 0, RRDATA_BYTES);
  20         for(unsigned i = 0; i < 2 * RRDATA_BYTES; i++) {
  21                 unsigned x = rnd[i];
  22                 x = x & 0x1F;
  23                 x = x - x / 16 * 9 - 1;
  24                 bytes[i / 2] = 16 * bytes[i / 2] + x;
  25         }
  26 }
  27
  28 rrdata::instance::instance(unsigned char* b) throw()
  29 {
  30         memcpy(bytes, b, RRDATA_BYTES);
  31 }
  32
  33 bool rrdata::instance::operator<(const struct instance& i) const throw()
  34 {
  35         for(unsigned j = 0; j < RRDATA_BYTES; j++)
  36                 if(bytes[j] < i.bytes[j])
  37                         return true;
  38                 else if(bytes[j] > i.bytes[j])
  39                         return false;
  40         return false;
  41 }
  42
  43 bool rrdata::instance::operator==(const struct instance& i) const throw()
  44 {
  45         for(unsigned j = 0; j < RRDATA_BYTES; j++)
  46                 if(bytes[j] != i.bytes[j])
  47                         return false;
  48         return true;
  49 }
  50
  51 const struct rrdata::instance rrdata::instance::operator++(int) throw()
  52 {
  53         instance i = *this;
  54         ++*this;
  55         return i;
  56 }
  57
  58 struct rrdata::instance& rrdata::instance::operator++() throw()
  59 {
  60         unsigned carry = 1;
  61         for(unsigned i = 31; i < 32; i--) {
  62                 unsigned newcarry = (bytes[i] == 255 && carry);
  63                 bytes[i] += carry;
  64                 carry = newcarry;
  65         }
  66         return *this;
  67 }
  68
  69 namespace
  70 {
  71         std::set<rrdata::instance> rrset;
  72         std::ifstream ihandle;
  73         std::ofstream ohandle;
  74         bool handle_open;
  75         std::string current_project;
  76 }
  77
  78 void rrdata::read_base(const std::string& project) throw(std::bad_alloc)
  79 {
  80         if(project == current_project)
  81                 return;
  82         std::set<rrdata::instance> new_rrset;
  83         std::string filename = get_config_path() + "/" + project + ".rr";
  84         if(handle_open) {
  85                 ohandle.close();
  86                 handle_open = false;
  87         }
  88         ihandle.open(filename.c_str(), std::ios_base::in);
  89         while(ihandle) {
  90                 unsigned char bytes[RRDATA_BYTES];
  91                 ihandle.read(reinterpret_cast<char*>(bytes), RRDATA_BYTES);
  92                 instance k(bytes);
  93                 //std::cerr << "Loaded symbol: " << k << std::endl;
  94                 new_rrset.insert(k);
  95         }
  96         ihandle.close();
  97         ohandle.open(filename.c_str(), std::ios_base::out | std::ios_base::app);
  98         if(ohandle)
  99                 handle_open = true;
 100         rrset = new_rrset;
 101         current_project = project;
 102 }
 103
 104 void rrdata::close() throw()
 105 {
 106         current_project = "";
 107         if(handle_open)
 108                 ohandle.close();
 109         handle_open = false;
 110 }
 111
 112 void rrdata::add(const struct rrdata::instance& i) throw(std::bad_alloc)
 113 {
 114         if(rrset.insert(i).second && handle_open) {
 115                 //std::cerr << "New symbol: " << i << std::endl;
 116                 ohandle.write(reinterpret_cast<const char*>(i.bytes), RRDATA_BYTES);
 117                 ohandle.flush();
 118         }
 119 }
 120
 121 void rrdata::add_internal() throw(std::bad_alloc)
 122 {
 123         if(!internal)
 124                 internal = new instance();
 125         add((*internal)++);
 126 }
 127
 128 namespace
 129 {
 130         void flush_symbol(std::vector<char>& strm, const rrdata::instance& base, const rrdata::instance& predicted,
 131                 unsigned count)
 132         {
 133                 char opcode;
 134                 char buf1[RRDATA_BYTES + 4];
 135                 char buf2[3];
 136                 unsigned bias;
 137                 if(count == 1) {
 138                         opcode = 0x00;
 139                         bias = 1;
 140                 } else if(count < 258) {
 141                         opcode = 0x20;
 142                         bias = 2;
 143                 } else if(count < 65794) {
 144                         opcode = 0x40;
 145                         bias = 258;
 146                 } else {
 147                         opcode = 0x60;
 148                         bias = 65794;
 149                 }
 150                 unsigned j;
 151                 for(j = 0; j < 31; j++)
 152                         if(base.bytes[j] != predicted.bytes[j])
 153                                 break;
 154                 opcode += j;
 155                 buf1[0] = opcode;
 156                 memcpy(buf1 + 1, base.bytes + j, RRDATA_BYTES - j);
 157                 buf2[0] = (count - bias) >> 16;
 158                 buf2[1] = (count - bias) >> 8;
 159                 buf2[2] = (count - bias);
 160                 memcpy(buf1 + (RRDATA_BYTES - j + 1), buf2 + (3 - (opcode >> 5)), opcode >> 5);
 161                 for(size_t s = 0; s < (RRDATA_BYTES - j + 1) + (opcode >> 5); s++)
 162                         strm.push_back(buf1[s]);
 163                 //std::cerr << "Encoding " << count << " symbols starting from " << base << std::endl;
 164         }
 165 }
 166
 167 uint64_t rrdata::write(std::vector<char>& strm) throw(std::bad_alloc)
 168 {
 169         strm.clear();
 170         uint64_t count = 0;
 171         instance last_encode_end;
 172         memset(last_encode_end.bytes, 0, RRDATA_BYTES);
 173
 174         instance predicted;
 175         instance encode_base;
 176         unsigned encode_count = 0;
 177         for(auto i : rrset) {
 178                 //std::cerr << "Considering " << *i << std::endl;
 179                 count++;
 180                 if(encode_count == 0) {
 181                         //This is the first symbol.
 182                         encode_base = i;
 183                         encode_count = 1;
 184                 } else if(predicted == i && encode_count < 16843009) {
 185                         //Correct prediction.
 186                         encode_count++;
 187                 } else {
 188                         //Failed prediction
 189                         flush_symbol(strm, encode_base, last_encode_end, encode_count);
 190                         last_encode_end = predicted;
 191                         encode_base = i;
 192                         encode_count = 1;
 193                 }
 194                 predicted = i;
 195                 ++predicted;
 196         }
 197         if(encode_count > 0)
 198                 flush_symbol(strm, encode_base, last_encode_end, encode_count);
 199         if(count)
 200                 return count - 1;
 201         else
 202                 return 0;
 203 }
 204
 205 uint64_t rrdata::read(std::vector<char>& strm, bool dummy) throw(std::bad_alloc)
 206 {
 207         uint64_t count = 0;
 208         instance decoding;
 209         uint64_t ptr = 0;
 210         memset(decoding.bytes, 0, RRDATA_BYTES);
 211         while(ptr < strm.size()) {
 212                 char opcode;
 213                 char buf1[RRDATA_BYTES];
 214                 char buf2[3];
 215                 opcode = strm[ptr++];
 216                 unsigned validbytes = (opcode & 0x1F);
 217                 unsigned lengthbytes = (opcode & 0x60) >> 5;
 218                 unsigned repeat = 1;
 219                 memcpy(buf1, &strm[ptr], RRDATA_BYTES - validbytes);
 220                 ptr += (RRDATA_BYTES - validbytes);
 221                 memcpy(decoding.bytes + validbytes, buf1, RRDATA_BYTES - validbytes);
 222                 if(lengthbytes > 0) {
 223                         memcpy(buf2, &strm[ptr], lengthbytes);
 224                         ptr += lengthbytes;
 225                 }
 226                 if(lengthbytes == 1)
 227                         repeat = 2 + buf2[0];
 228                 if(lengthbytes == 2)
 229                         repeat = 258 + static_cast<unsigned>(buf2[0]) * 256 + buf2[1];
 230                 if(lengthbytes == 3)
 231                         repeat = 65794 + static_cast<unsigned>(buf2[0]) * 65536 + static_cast<unsigned>(buf2[1]) *
 232                                 256 + buf2[2];
 233                 //std::cerr << "Decoding " << count << " symbols starting from " << decoding << std::endl;
 234                 if(!dummy)
 235                         for(unsigned i = 0; i < repeat; i++)
 236                                 rrdata::add(decoding++);
 237                 count += repeat;
 238         }
 239         if(count)
 240                 return count - 1;
 241         else
 242                 return 0;
 243 }
 244
 245 uint64_t rrdata::count(std::vector<char>& strm) throw(std::bad_alloc)
 246 {
 247         return read(strm, true);
 248 }
 249
 250 const char* hexes = "0123456789ABCDEF";
 251
 252 std::ostream& operator<<(std::ostream& os, const struct rrdata::instance& j)
 253 {
 254         for(unsigned i = 0; i < 32; i++) {
 255                 os << hexes[j.bytes[i] / 16] << hexes[j.bytes[i] % 16];
 256         }
 257         return os;
 258 }
 259
 260 rrdata::instance* rrdata::internal;
 261
 262
 263 //DBC0AB8CBAAC6ED4B7781E34057891E8B9D93AAE733DEF764C06957FF705DE00
 264 //DBC0AB8CBAAC6ED4B7781E34057891E8B9D93AAE733DEF764C06957FF705DDF3