integer.hpp

00001 /*
00002 This file is part of GraphLab.
00003 
00004 GraphLab is free software: you can redistribute it and/or modify
00005 it under the terms of the GNU Lesser General Public License as 
00006 published by the Free Software Foundation, either version 3 of 
00007 the License, or (at your option) any later version.
00008 
00009 GraphLab is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 GNU Lesser General Public License for more details.
00013 
00014 You should have received a copy of the GNU Lesser General Public 
00015 License along with GraphLab.  If not, see <http://www.gnu.org/licenses/>.
00016 */
00017 
00018 #ifndef INTEGER_HPP
00019 #define INTEGER_HPP
00020 #include <stdint.h>
00021 #include <graphlab/logger/assertions.hpp>
00022 namespace graphlab {
00023 inline unsigned char compress_int(uint64_t u, char output[10]) {
00024   // if 1st bit of u is set. could be negative,
00025   // flip all the bits if it is
00026   uint64_t isneg = (uint64_t)((int64_t)(u) >> 63);
00027   // if first bit of u is set, isneg = -1.......
00028   // otherwise isneg = 0....
00029   u = (u ^ isneg) - isneg;
00030   
00031   // get the largest bit
00032   int nbits = 0;
00033   if (u != 0) nbits = (64 - __builtin_clzll(u));
00034   
00035   //std::cout << (int)nbits << "\t"; 
00036   //std::cout.flush();
00037   // divide by 7. quickly
00038   // this is the number of bytes I need. The second one is actually rather ingenious
00039   // "lookup table" faster than "magic number" faster than "division"
00040   //unsigned char c = (nbits + 6) / 7 + (nbits == 0);
00041   //unsigned char c = (nbits >> 3) + 1 + ((0xfefcf8f0e0c08000ULL & (1ULL << nbits)) > 0);
00042   static const unsigned char lookuptable[64] = {1,1,1,1,1,1,1,1,
00043                                                 2,2,2,2,2,2,2,
00044                                                 3,3,3,3,3,3,3,
00045                                                 4,4,4,4,4,4,4,
00046                                                 5,5,5,5,5,5,5,
00047                                                 6,6,6,6,6,6,6,
00048                                                 7,7,7,7,7,7,7,
00049                                                 8,8,8,8,8,8,8,
00050                                                 9,9,9,9,9,9,9};
00051   unsigned char c = lookuptable[nbits];
00052   
00053   switch(c) {
00054     case 9:
00055       output[1] = (char)((u & (0x7FLL << 56)) >> 56);
00056     case 8:
00057       output[2] = (char)((u & (0x7FLL << 49)) >> 49);
00058     case 7:
00059       output[3] = (char)((u & (0x7FLL << 42)) >> 42);
00060     case 6:
00061       output[4] = (char)((u & (0x7FLL << 35)) >> 35);
00062     case 5:
00063       output[5] = (char)((u & (0x7FLL << 28)) >> 28);
00064     case 4:
00065       output[6] = (char)(((unsigned uint32_t)(u) & (0x7FLL << 21)) >> 21); 
00066     case 3:
00067       output[7] = (char)(((unsigned uint32_t)(u) & (0x7FLL << 14)) >> 14);
00068     case 2:
00069       output[8] = (char)(((unsigned short)(u) & (0x7FLL << 7)) >> 7);
00070     case 1:
00071       output[9] = (char)(((unsigned char)(u) & 0x7F) | 0x80); // set the bit in the least significant 
00072   }
00073   
00074   if (isneg == 0) {
00075     return c;
00076   }
00077   else {
00078     output[9 - c] = 0;
00079     return (unsigned char)(c + 1);
00080   }
00081 }
00082 
00083 
00084 
00085 template <typename IntType>
00086 inline void decompress_int(const char* arr, IntType &ret) {
00087   // if 1st bit of u is set. could be negative,
00088   // flip all the bits if it is
00089   bool isneg = (arr[0] == 0);
00090   if (isneg) ++arr;
00091   
00092   ret = 0;
00093   while(1) {
00094     ret = (ret << 7) | ((*arr) & 0x7F);
00095     if ((*arr) & 0x80) break;
00096     ++arr;
00097   };
00098   if (isneg)  ret = -ret;
00099 }
00100 
00101 template <typename IntType>
00102 inline void decompress_int_from_ref(const char* &arr, IntType &ret) {
00103   // if 1st bit of u is set. could be negative,
00104   // flip all the bits if it is
00105   bool isneg = (arr[0] == 0);
00106   if (isneg) ++arr;
00107   
00108   ret = 0;
00109   while(1) {
00110     ret = (ret << 7) | ((*arr) & 0x7F);
00111     if ((*arr) & 0x80) break;
00112     ++arr;
00113   };
00114   if (isneg)  ret = -ret;
00115   ++arr;
00116 }
00117 
00118 
00119 template <typename IntType>
00120 inline void decompress_int(std::istream &strm, IntType &ret) {
00121   // if 1st bit of u is set. could be negative,
00122   // flip all the bits if it is
00123   char c = (char)strm.peek();
00124   bool isneg = (c == 0);
00125   if (isneg) strm.get(c);
00126   
00127   ret = 0;
00128   while(1) {
00129     strm.get(c);
00130     ret = (IntType)((ret << 7) | (c & 0x7F));
00131     if (c & 0x80) break;
00132   };
00133   if (isneg)  ret = (IntType)(-ret);
00134 }
00135 
00136 
00137 }
00138 
00139 
00140 
00141 #endif
00142