The Tor Browser / file revision

 // Copyright 2013 Google Inc. All Rights Reserved.

 //

 // Licensed under the Apache License, Version 2.0 (the "License");

 // you may not use this file except in compliance with the License.

 // You may obtain a copy of the License at

 //

 //     http://www.apache.org/licenses/LICENSE-2.0

 //

 // Unless required by applicable law or agreed to in writing, software

 // distributed under the License is distributed on an "AS IS" BASIS,

 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

 // See the License for the specific language governing permissions and

 // limitations under the License.

 //

 // Author: dsites@google.com (Dick Sites)

 //

 #include "tote.h"

 #include "lang_script.h"    // For LanguageCode in Dump

 #include <stdio.h>

 #include <string.h>         // For memset

 namespace CLD2 {

 // Take a set of <key, value> pairs and tote them up.

 // After explicitly sorting, retrieve top key, value pairs

 // Normal use is key=per-script language and value = probability score

 Tote::Tote() {

   in_use_mask_ = 0;

   byte_count_ = 0;

   score_count_ = 0;

   // No need to initialize values

 }

 Tote::~Tote() {

 }

 void Tote::Reinit() {

   in_use_mask_ = 0;

   byte_count_ = 0;

   score_count_ = 0;

   // No need to initialize values

 }

 // Increment count of quadgrams/trigrams/unigrams scored

 void Tote::AddScoreCount() {

   ++score_count_;

 }

 void Tote::Add(uint8 ikey, int idelta) {

   int key_group = ikey >> 2;

   uint64 groupmask = (1ULL << key_group);

   if ((in_use_mask_ & groupmask) == 0) {

     // Initialize this group

     gscore_[key_group] = 0;

     in_use_mask_ |= groupmask;

   }

   score_[ikey] += idelta;

 }

 // Return current top three keys

 void Tote::CurrentTopThreeKeys(int* key3) const {

   key3[0] = -1;

   key3[1] = -1;

   key3[2] = -1;

   int score3[3] = {-1, -1, -1};

   uint64 tempmask = in_use_mask_;

   int base = 0;

   while (tempmask != 0) {

     if (tempmask & 1) {

       // Look at four in-use keys

       for (int i = 0; i < 4; ++i) {

         int insert_me = score_[base + i];

         // Favor lower numbers on ties

         if (insert_me > score3[2]) {

           // Insert

           int insert_at = 2;

           if (insert_me > score3[1]) {

             score3[2] = score3[1];

             key3[2] = key3[1];

             insert_at = 1;

             if (insert_me > score3[0]) {

               score3[1] = score3[0];

               key3[1] = key3[0];

               insert_at = 0;

             }

           }

           score3[insert_at] = insert_me;

           key3[insert_at] = base + i;

         }

       }

     }

     tempmask >>= 1;

     base += 4;

   }

 }

 // Take a set of <key, value> pairs and tote them up.

 // After explicitly sorting, retrieve top key, value pairs

 // 0xFFFF in key signifies unused

 DocTote::DocTote() {

   // No need to initialize score_ or value_

   incr_count_ = 0;

   sorted_ = 0;

   memset(closepair_, 0, sizeof(closepair_));

   memset(key_, 0xFF, sizeof(key_));

 }

 DocTote::~DocTote() {

 }

 void DocTote::Reinit() {

   // No need to initialize score_ or value_

   incr_count_ = 0;

   sorted_ = 0;

   memset(closepair_, 0, sizeof(closepair_));

   memset(key_, 0xFF, sizeof(key_));

   runningscore_.Reinit();

 }

 // Weight reliability by ibytes

 // Also see three-way associative comments above for Tote

 void DocTote::Add(uint16 ikey, int ibytes,

                               int score, int ireliability) {

   ++incr_count_;

   // Look for existing entry in top 2 positions of 3, times 8 columns

   int sub0 = ikey & 15;

   if (key_[sub0] == ikey) {

     value_[sub0] += ibytes;

     score_[sub0] += score;

     reliability_[sub0] += ireliability * ibytes;

     return;

   }

   // Look for existing entry in other of top 2 positions of 3, times 8 columns

   int sub1 = sub0 ^ 8;

   if (key_[sub1] == ikey) {

     value_[sub1] += ibytes;

     score_[sub1] += score;

     reliability_[sub1] += ireliability * ibytes;

     return;

   }

   // Look for existing entry in third position of 3, times 8 columns

   int sub2 = (ikey & 7) + 16;

   if (key_[sub2] == ikey) {

     value_[sub2] += ibytes;

     score_[sub2] += score;

     reliability_[sub2] += ireliability * ibytes;

     return;

   }

   // Allocate new entry

   int alloc = -1;

   if (key_[sub0] == kUnusedKey) {

     alloc = sub0;

   } else if (key_[sub1] == kUnusedKey) {

     alloc = sub1;

   } else if (key_[sub2] == kUnusedKey) {

     alloc = sub2;

   } else {

     // All choices allocated, need to replace smallest one

     alloc = sub0;

     if (value_[sub1] < value_[alloc]) {alloc = sub1;}

     if (value_[sub2] < value_[alloc]) {alloc = sub2;}

   }

   key_[alloc] = ikey;

   value_[alloc] = ibytes;

   score_[alloc] = score;

   reliability_[alloc] = ireliability * ibytes;

   return;

 }

 // Find subscript of a given packed language, or -1

 int DocTote::Find(uint16 ikey) {

   if (sorted_) {

     // Linear search if sorted

     for (int sub = 0; sub < kMaxSize_; ++sub) {

       if (key_[sub] == ikey) {return sub;}

     }

     return -1;

   }

   // Look for existing entry

   int sub0 = ikey & 15;

   if (key_[sub0] == ikey) {

     return sub0;

   }

   int sub1 = sub0 ^ 8;

   if (key_[sub1] == ikey) {

     return sub1;

   }

   int sub2 = (ikey & 7) + 16;

   if (key_[sub2] == ikey) {

     return sub2;

   }

   return -1;

 }

 // Return current top key

 int DocTote::CurrentTopKey() {

   int top_key = 0;

   int top_value = -1;

   for (int sub = 0; sub < kMaxSize_; ++sub) {

     if (key_[sub] == kUnusedKey) {continue;}

     if (top_value < value_[sub]) {

       top_value = value_[sub];

       top_key = key_[sub];

     }

   }

   return top_key;

 }

 // Sort first n entries by decreasing order of value

 // If key==0 other fields are not valid, treat value as -1

 void DocTote::Sort(int n) {

   // This is n**2, but n is small

   for (int sub = 0; sub < n; ++sub) {

     if (key_[sub] == kUnusedKey) {value_[sub] = -1;}

     // Bubble sort key[sub] and entry[sub]

     for (int sub2 = sub + 1; sub2 < kMaxSize_; ++sub2) {

       if (key_[sub2] == kUnusedKey) {value_[sub2] = -1;}

       if (value_[sub] < value_[sub2]) {

         // swap

         uint16 tmpk = key_[sub];

         key_[sub] = key_[sub2];

         key_[sub2] = tmpk;

         int tmpv = value_[sub];

         value_[sub] = value_[sub2];

         value_[sub2] = tmpv;

         double tmps = score_[sub];

         score_[sub] = score_[sub2];

         score_[sub2] = tmps;

         int tmpr = reliability_[sub];

         reliability_[sub] = reliability_[sub2];

         reliability_[sub2] = tmpr;

       }

     }

   }

   sorted_ = 1;

 }

 void DocTote::Dump(FILE* f) {

   fprintf(f, "DocTote::Dump\n");

   for (int sub = 0; sub < kMaxSize_; ++sub) {

     if (key_[sub] != kUnusedKey) {

       Language lang = static_cast<Language>(key_[sub]);

       fprintf(f, "[%2d] %3s %6dB %5dp %4dR,\n", sub, LanguageCode(lang),

               value_[sub], score_[sub], reliability_[sub]);

     }

   }

   fprintf(f, "  %d chunks scored<br>\n", incr_count_);

 }

 }       // End namespace CLD2