LCOV - code coverage report
Current view: top level - home/snapwebsites/snapcpp/snapwebsites/snapdatabase/snapdatabase/file - hash.cpp (source / functions) Hit Total Coverage
Test: coverage.info Lines: 0 144 0.0 %
Date: 2019-12-15 17:13:15 Functions: 0 8 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : // Copyright (c) 2019  Made to Order Software Corp.  All Rights Reserved
       2             : //
       3             : // https://snapwebsites.org/project/snapdatabase
       4             : // contact@m2osw.com
       5             : //
       6             : // This program is free software; you can redistribute it and/or modify
       7             : // it under the terms of the GNU General Public License as published by
       8             : // the Free Software Foundation; either version 2 of the License, or
       9             : // (at your option) any later version.
      10             : //
      11             : // This program is distributed in the hope that it will be useful,
      12             : // but WITHOUT ANY WARRANTY; without even the implied warranty of
      13             : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14             : // GNU General Public License for more details.
      15             : //
      16             : // You should have received a copy of the GNU General Public License along
      17             : // with this program; if not, write to the Free Software Foundation, Inc.,
      18             : // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
      19             : 
      20             : 
      21             : /** \file
      22             :  * \brief Database file implementation.
      23             :  *
      24             :  * Each table uses one or more files. Each file is handled by a dbfile
      25             :  * object and a corresponding set of blocks.
      26             :  */
      27             : 
      28             : // self
      29             : //
      30             : #include    "snapdatabase/file/hash.h"
      31             : 
      32             : #include    "snapdatabase/exception.h"
      33             : 
      34             : // C lib
      35             : //
      36             : #include    <string.h>
      37             : 
      38             : // last include
      39             : //
      40             : #include    <snapdev/poison.h>
      41             : 
      42             : 
      43             : 
      44             : namespace snapdatabase
      45             : {
      46             : 
      47             : 
      48             : constexpr hash_t        END_OF_BUFFER = static_cast<hash_t>(-1);
      49             : 
      50             : 
      51             : /** \brief Init the hash with the specified seed.
      52             :  *
      53             :  * The hash class starts with the specified seed. By changing the seed
      54             :  * you can reuse the same class as if you were using several different
      55             :  * hash functions. This is how we create multiple hashes for bloom
      56             :  * filters.
      57             :  *
      58             :  * \param[in] seed  The seed to start with.
      59             :  */
      60           0 : hash::hash(hash_t seed)
      61           0 :     : f_hash(seed)
      62             : {
      63           0 : }
      64             : 
      65             : 
      66           0 : hash_t hash::get_byte() const
      67             : {
      68           0 :     if(f_temp_size > 0)
      69             :     {
      70           0 :         --f_temp_size;
      71           0 :         return f_temp[f_temp_size];
      72             :     }
      73             : 
      74           0 :     if(f_size > 0)
      75             :     {
      76           0 :         uint8_t const v(*f_buffer);
      77           0 :         ++f_buffer;
      78           0 :         --f_size;
      79           0 :         return v;
      80             :     }
      81             : 
      82           0 :     return END_OF_BUFFER;
      83             : }
      84             : 
      85             : 
      86           0 : hash_t hash::peek_byte(int pos) const
      87             : {
      88           0 :     if(static_cast<std::size_t>(pos) < f_temp_size)
      89             :     {
      90             :         // bytes are in reverse order in f_temp
      91             :         //
      92           0 :         return f_temp[f_temp_size - pos - 1];
      93             :     }
      94           0 :     pos -= f_temp_size;
      95             : 
      96           0 :     if(static_cast<std::size_t>(pos) < f_size)
      97             :     {
      98           0 :         return f_buffer[pos];
      99             :     }
     100             : 
     101           0 :     return 0;
     102             : }
     103             : 
     104             : 
     105           0 : size_t hash::size() const
     106             : {
     107           0 :     return f_temp_size + f_size;
     108             : }
     109             : 
     110             : 
     111           0 : void hash::get_64bits(hash_t & v1, hash_t & v2)
     112             : {
     113           0 :     if(f_temp_size == 0 && f_size >= 8)
     114             :     {
     115             :         // faster this way
     116             :         //
     117           0 :         v1 = (f_buffer[0] << 24)
     118           0 :            + (f_buffer[1] << 16)
     119           0 :            + (f_buffer[2] <<  8)
     120           0 :            + (f_buffer[3] <<  0);
     121             : 
     122           0 :         v2 = (f_buffer[4] << 24)
     123           0 :            + (f_buffer[5] << 16)
     124           0 :            + (f_buffer[6] <<  8)
     125           0 :            + (f_buffer[7] <<  0);
     126             : 
     127           0 :         f_buffer += 8;
     128           0 :         f_size -= 8;
     129             : 
     130           0 :         return;
     131             :     }
     132             : 
     133           0 :     if(size() >= 8)
     134             :     {
     135           0 :         v1 = (get_byte() << 24)
     136           0 :            + (get_byte() << 16)
     137           0 :            + (get_byte() <<  8)
     138           0 :            + (get_byte() <<  0);
     139             : 
     140           0 :         v2 = (get_byte() << 24)
     141           0 :            + (get_byte() << 16)
     142           0 :            + (get_byte() <<  8)
     143           0 :            + (get_byte() <<  0);
     144             : 
     145           0 :         return;
     146             :     }
     147             : 
     148           0 :     throw snapdatabase_logic_error("called get_64bits() when the input buffer is less than 64 bits");
     149             : }
     150             : 
     151             : 
     152           0 : void hash::peek_64bits(hash_t & v1, hash_t & v2) const
     153             : {
     154           0 :     switch(size())
     155             :     {
     156           0 :     case 7:
     157           0 :         v1 = (get_byte() << 24)
     158           0 :            + (get_byte() << 16)
     159           0 :            + (get_byte() <<  8)
     160           0 :            + (get_byte() <<  0);
     161             : 
     162           0 :         v2 = (get_byte() << 16)
     163           0 :            + (get_byte() <<  8)
     164           0 :            + (get_byte() <<  0);
     165           0 :         break;
     166             : 
     167           0 :     case 6:
     168           0 :         v1 = (get_byte() << 24)
     169           0 :            + (get_byte() << 16)
     170           0 :            + (get_byte() <<  8)
     171           0 :            + (get_byte() <<  0);
     172             : 
     173           0 :         v2 = (get_byte() <<  8)
     174           0 :            + (get_byte() <<  0);
     175           0 :         break;
     176             : 
     177           0 :     case 5:
     178           0 :         v1 = (get_byte() << 24)
     179           0 :            + (get_byte() << 16)
     180           0 :            + (get_byte() <<  8)
     181           0 :            + (get_byte() <<  0);
     182             : 
     183           0 :         v2 = (get_byte() <<  0);
     184           0 :         break;
     185             : 
     186           0 :     case 4:
     187           0 :         v1 = (get_byte() << 24)
     188           0 :            + (get_byte() << 16)
     189           0 :            + (get_byte() <<  8)
     190           0 :            + (get_byte() <<  0);
     191             : 
     192           0 :         v2 = 0;
     193           0 :         break;
     194             : 
     195           0 :     case 3:
     196           0 :         v1 = (get_byte() << 16)
     197           0 :            + (get_byte() <<  8)
     198           0 :            + (get_byte() <<  0);
     199             : 
     200           0 :         v2 = 0;
     201           0 :         break;
     202             : 
     203           0 :     case 2:
     204           0 :         v1 = (get_byte() <<  8)
     205           0 :            + (get_byte() <<  0);
     206             : 
     207           0 :         v2 = 0;
     208           0 :         break;
     209             : 
     210           0 :     case 1:
     211           0 :         v1 = (get_byte() <<  0);
     212             : 
     213           0 :         v2 = 0;
     214           0 :         break;
     215             : 
     216           0 :     case 0:
     217           0 :         v1 = 0;
     218           0 :         v2 = 0;
     219           0 :         break;
     220             : 
     221           0 :     default:
     222           0 :         throw snapdatabase_logic_error("called peek_64bits() when the input buffer is 64 bits or more");
     223             : 
     224             :     }
     225           0 : }
     226             : 
     227             : 
     228             : // hash function taken from: https://github.com/ArashPartow/bloom
     229             : // and modified to work incrementally.
     230             : //
     231           0 : void hash::add(uint8_t const * v, std::size_t buffer_size)
     232             : {
     233           0 :     f_buffer = v;
     234           0 :     f_size = buffer_size;
     235             : 
     236           0 :     while(size() >= 8)
     237             :     {
     238           0 :         hash_t v1(0);
     239           0 :         hash_t v2(0);
     240           0 :         get_64bits(v1, v2);
     241             : 
     242           0 :         f_hash ^= (f_hash <<  7) ^ (v1 * (f_hash >> 3))
     243           0 :              ^ (~((f_hash << 11) + (v2 ^ (f_hash >> 5))));
     244             :     }
     245             : 
     246           0 :     if(f_temp_size > 0 && f_size > 0)
     247             :     {
     248           0 :         memmove(f_temp + f_size, f_temp, f_temp_size);
     249             :     }
     250             : 
     251           0 :     f_temp_size += f_size;
     252           0 :     for(int in(0); f_size > 0; ++in)
     253             :     {
     254           0 :         --f_size;
     255           0 :         f_temp[in] = f_buffer[f_size];
     256             :     }
     257           0 : }
     258             : 
     259             : 
     260           0 : hash_t hash::get() const
     261             : {
     262           0 :     hash_t h(f_hash);
     263             : 
     264           0 :     std::size_t sz(size());
     265           0 :     if(sz > 0)
     266             :     {
     267           0 :         hash_t loop(0);
     268             :         hash_t v1;
     269             :         hash_t v2;
     270           0 :         peek_64bits(v1, v2);
     271             : 
     272           0 :         if(sz >= 4)
     273             :         {
     274           0 :             h ^= ~((h << 11) + (v1 ^ (h >> 5)));
     275           0 :             ++loop;
     276             : 
     277           0 :             sz -= 4;
     278           0 :             v1 = v2;
     279             :         }
     280             : 
     281           0 :         if(sz >= 3)
     282             :         {
     283           0 :             v2 = v1 >> 8;
     284           0 :             if(loop != 0)
     285             :             {
     286           0 :                 h ^=    (h <<  7) ^  v2 * (h >> 3);
     287             :             }
     288             :             else
     289             :             {
     290           0 :                 h ^= (~((h << 11) + (v2 ^ (h >> 5))));
     291             :             }
     292           0 :             ++loop;
     293             : 
     294           0 :             sz = 1;
     295           0 :             v1 &= 255;
     296             :         }
     297           0 :         else if(sz == 2)
     298             :         {
     299           0 :             if(loop != 0)
     300             :             {
     301           0 :                 h ^=    (h <<  7) ^  v1 * (h >> 3);
     302             :             }
     303             :             else
     304             :             {
     305           0 :                 h ^= (~((h << 11) + (v1 ^ (h >> 5))));
     306             :             }
     307             :             //++loop; -- not necessary, we won't reuse it
     308             : 
     309           0 :             sz = 0;
     310             :         }
     311             : 
     312           0 :         if(sz > 0)
     313             :         {
     314           0 :             h += (v1 ^ (h * 0xA5A5A5A5)) + loop;
     315             :         }
     316             :     }
     317             : 
     318           0 :     return h;
     319             : }
     320             : 
     321             : 
     322             : 
     323             : } // namespace snapdatabase
     324             : // vim: ts=4 sw=4 et

Generated by: LCOV version 1.13