encodings/compact_lang_det/cldutil.cc

// Copyright (c) 2009 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include <string>
#include "encodings/compact_lang_det/cldutil.h"

#include "base/basictypes.h"
#include "encodings/compact_lang_det/cldutil_dbg.h"
#include "encodings/compact_lang_det/generated/compact_lang_det_generated_meanscore.h"
#include "encodings/compact_lang_det/utf8propletterscriptnum.h"
#include "encodings/compact_lang_det/win/cld_commandlineflags.h"
#include "encodings/compact_lang_det/win/cld_logging.h"
#include "encodings/compact_lang_det/win/cld_unilib.h"
#include "encodings/compact_lang_det/win/cld_utf.h"
#include "encodings/compact_lang_det/win/cld_utf8statetable.h"

// Runtime routines for hashing, looking up, and scoring
// unigrams (CJK), bigrams (CJK), quadgrams, and octagrams.
// Unigrams and bigrams are for CJK languages only, including simplified/
// traditional Chinese, Japanese, Korean, Vietnamese Han characters, and
// Zhuang Han characters. Surrounding spaces are not considered.
// Quadgrams and octagrams for for non-CJK and include two bits indicating
// preceding and trailing spaces (word boundaries).


// Indicator bits for leading/trailing space around quad/octagram
// NOTE: 4444 bits are chosen to flip constant bits in hash of four chars of
// 1-, 2-, or 3-bytes each.
static const uint32 kPreSpaceIndicator =  0x00004444;
static const uint32 kPostSpaceIndicator = 0x44440000;

// Little-endian masks for 0..24 bytes picked up as uint32's
static const uint32 kWordMask0[4] = {
  0xFFFFFFFF, 0x000000FF, 0x0000FFFF, 0x00FFFFFF
};

static const int kMinCJKUTF8CharBytes = 3;

static const int kMinGramCount = 3;
static const int kMaxGramCount = 16;


// Routines to access a hash table of <key:wordhash, value:probs> pairs
// Buckets have 4-byte wordhash for sizes < 32K buckets, but only
// 2-byte wordhash for sizes >= 32K buckets, with other wordhash bits used as
// bucket subscript.
// Probs is a packed: three languages plus a subscript for probability table
// Buckets have all the keys together, then all the values.Key array never
// crosses a cache-line boundary, so no-match case takes exactly one cache miss.
// Match case may sometimes take an additional cache miss on value access.
//
// Other possibilites include 5 or 10 6-byte entries plus pad to make 32 or 64
// byte buckets with single cache miss.
// Or 2-byte key and 6-byte value, allowing 5 languages instead  of three.
//------------------------------------------------------------------------------


//------------------------------------------------------------------------------
// Hashing groups of 1/2/4/8 letters, perhaps with spaces or underscores
//------------------------------------------------------------------------------

// Design principles for these hash functions
// - Few operations
// - Handle 1-, 2-, and 3-byte UTF-8 scripts, ignoring intermixing except in
//   Latin script expect 1- and 2-byte mixtures.
// - Last byte of each character has about 5 bits of information
// - Spread good bits around so they can interact in at least two ways
//   with other characters
// - Use add for additional mixing thorugh carries

// CJK Three-byte bigram
//   ....dddd..cccccc..bbbbbb....aaaa
//   ..................ffffff..eeeeee
// make
//   ....dddd..cccccc..bbbbbb....aaaa
//   000....dddd..cccccc..bbbbbb....a
//   ..................ffffff..eeeeee
//   ffffff..eeeeee000000000000000000
//
// CJK Four-byte bigram
//   ..dddddd..cccccc....bbbb....aaaa
//   ..hhhhhh..gggggg....ffff....eeee
// make
//   ..dddddd..cccccc....bbbb....aaaa
//   000..dddddd..cccccc....bbbb....a
//   ..hhhhhh..gggggg....ffff....eeee
//   ..ffff....eeee000000000000000000

// BIGRAM
// Pick up 1..8 bytes and hash them via mask/shift/add. NO pre/post
// OVERSHOOTS up to 3 bytes
// For runtime use of tables
uint32 cld::BiHashV25(const char* word_ptr, int bytecount) {
  if (bytecount == 0) {
    return 0;
  }
  uint32 word0, word1;
  if (bytecount <= 4) {
    word0 = UnalignedLoad32(word_ptr) & kWordMask0[bytecount & 3];
    word0 = word0 ^ (word0 >> 3);
    return word0;
  }
  // Else do 8 bytes
  word0 = UnalignedLoad32(word_ptr);
  word0 = word0 ^ (word0 >> 3);
  word1 = UnalignedLoad32(word_ptr + 4) & kWordMask0[bytecount & 3];
  word1 = word1 ^ (word1 << 18);
  return word0 + word1;
}

//
// Ascii-7 One-byte chars
//   ...ddddd...ccccc...bbbbb...aaaaa
// make
//   ...ddddd...ccccc...bbbbb...aaaaa
//   000...ddddd...ccccc...bbbbb...aa
//
// Latin 1- and 2-byte chars
//   ...ddddd...ccccc...bbbbb...aaaaa
//   ...................fffff...eeeee
// make
//   ...ddddd...ccccc...bbbbb...aaaaa
//   000...ddddd...ccccc...bbbbb...aa
//   ...................fffff...eeeee
//   ...............fffff...eeeee0000
//
// Non-CJK Two-byte chars
//   ...ddddd...........bbbbb........
//   ...hhhhh...........fffff........
// make
//   ...ddddd...........bbbbb........
//   000...ddddd...........bbbbb.....
//   ...hhhhh...........fffff........
//   hhhh...........fffff........0000
//
// Non-CJK Three-byte chars
//   ...........ccccc................
//   ...................fffff........
//   ...lllll...................iiiii
// make
//   ...........ccccc................
//   000...........ccccc.............
//   ...................fffff........
//   ...............fffff........0000
//   ...lllll...................iiiii
//   .lllll...................iiiii00
//

// QUADGRAM
// Pick up 1..12 bytes plus pre/post space and hash them via mask/shift/add
// OVERSHOOTS up to 3 bytes
// For runtime use of tables
uint32 QuadHashV25Mix(const char* word_ptr, int bytecount, uint32 prepost) {
  uint32 word0, word1, word2;
  if (bytecount <= 4) {
    word0 = UnalignedLoad32(word_ptr) & kWordMask0[bytecount & 3];
    word0 = word0 ^ (word0 >> 3);
    return word0 ^ prepost;
  } else if (bytecount <= 8) {
    word0 = UnalignedLoad32(word_ptr);
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4) & kWordMask0[bytecount & 3];
    word1 = word1 ^ (word1 << 4);
    return (word0 ^ prepost) + word1;
  }
  // else do 12 bytes
  word0 = UnalignedLoad32(word_ptr);
  word0 = word0 ^ (word0 >> 3);
  word1 = UnalignedLoad32(word_ptr + 4);
  word1 = word1 ^ (word1 << 4);
  word2 = UnalignedLoad32(word_ptr + 8) & kWordMask0[bytecount & 3];
  word2 = word2 ^ (word2 << 2);
  return (word0 ^ prepost) + word1 + word2;
}


// QUADGRAM wrapper with surrounding spaces
// Pick up 1..12 bytes plus pre/post space and hash them via mask/shift/add
// UNDERSHOOTS 1 byte, OVERSHOOTS up to 3 bytes
// For runtime use of tables
uint32 cld::QuadHashV25(const char* word_ptr, int bytecount) {
  if (bytecount == 0) {
    return 0;
  }
  uint32 prepost = 0;
  if (word_ptr[-1] == ' ') {prepost |= kPreSpaceIndicator;}
  if (word_ptr[bytecount] == ' ') {prepost |= kPostSpaceIndicator;}
  return QuadHashV25Mix(word_ptr, bytecount, prepost);
}

// QUADGRAM wrapper with surrounding underscores (offline use)
// Pick up 1..12 bytes plus pre/post '_' and hash them via mask/shift/add
// OVERSHOOTS up to 3 bytes
// For offline construction of tables
uint32 cld::QuadHashV25Underscore(const char* word_ptr, int bytecount) {
  if (bytecount == 0) {
    return 0;
  }
  const char* local_word_ptr = word_ptr;
  int local_bytecount = bytecount;
  uint32 prepost = 0;
  if (local_word_ptr[0] == '_') {
    prepost |= kPreSpaceIndicator;
    ++local_word_ptr;
    --local_bytecount;
  }
  if (local_word_ptr[local_bytecount - 1] == '_') {
    prepost |= kPostSpaceIndicator;
    --local_bytecount;
  }
  return QuadHashV25Mix(local_word_ptr, local_bytecount, prepost);
}


// OCTAGRAM
// Pick up 1..24 bytes plus pre/post space and hash them via mask/shift/add
// UNDERSHOOTS 1 byte, OVERSHOOTS up to 3 bytes
//
// The low 32 bits follow the pattern from above, tuned to different scripts
// The high 8 bits are a simple sum of all bytes, shifted by 0/1/2/3 bits each
// For runtime use of tables V3
uint64 OctaHash40Mix(const char* word_ptr, int bytecount, uint64 prepost) {
  uint64 word0;
  uint64 word1;
  uint64 sum;

  if (word_ptr[-1] == ' ') {prepost |= kPreSpaceIndicator;}
  if (word_ptr[bytecount] == ' ') {prepost |= kPostSpaceIndicator;}
  switch ((bytecount - 1) >> 2) {
  case 0:       // 1..4 bytes
    word0 = UnalignedLoad32(word_ptr) & kWordMask0[bytecount & 3];
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    break;
  case 1:       // 5..8 bytes
    word0 = UnalignedLoad32(word_ptr);
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4) & kWordMask0[bytecount & 3];
    sum += word1;
    word1 = word1 ^ (word1 << 4);
    word0 += word1;
    break;
  case 2:       // 9..12 bytes
    word0 = UnalignedLoad32(word_ptr);
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4);
    sum += word1;
    word1 = word1 ^ (word1 << 4);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 8) & kWordMask0[bytecount & 3];
    sum += word1;
    word1 = word1 ^ (word1 << 2);
    word0 += word1;
    break;
  case 3:       // 13..16 bytes
    word0 = UnalignedLoad32(word_ptr);
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4);
    sum += word1;
    word1 = word1 ^ (word1 << 4);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 8);
    sum += word1;
    word1 = word1 ^ (word1 << 2);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 12) & kWordMask0[bytecount & 3];
    sum += word1;
    word1 = word1 ^ (word1 >> 8);
    word0 += word1;
    break;
  case 4:       // 17..20 bytes
    word0 = UnalignedLoad32(word_ptr);
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4);
    sum += word1;
    word1 = word1 ^ (word1 << 4);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 8);
    sum += word1;
    word1 = word1 ^ (word1 << 2);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 12);
    sum += word1;
    word1 = word1 ^ (word1 >> 8);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 16) & kWordMask0[bytecount & 3];
    sum += word1;
    word1 = word1 ^ (word1 >> 4);
    word0 += word1;
    break;
  default:      // 21..24 bytes and higher (ignores beyond 24)
    word0 = UnalignedLoad32(&word_ptr);
    sum = word0;
    word0 = word0 ^ (word0 >> 3);
    word1 = UnalignedLoad32(word_ptr + 4);
    sum += word1;
    word1 = word1 ^ (word1 << 4);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 8);
    sum += word1;
    word1 = word1 ^ (word1 << 2);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 12);
    sum += word1;
    word1 = word1 ^ (word1 >> 8);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 16);
    sum += word1;
    word1 = word1 ^ (word1 >> 4);
    word0 += word1;
    word1 = UnalignedLoad32(word_ptr + 20) & kWordMask0[bytecount & 3];
    sum += word1;
    word1 = word1 ^ (word1 >> 6);
    word0 += word1;
    break;
  }

  sum += (sum >> 17);             // extra 1-bit shift for bytes 2 & 3
  sum += (sum >> 9);              // extra 1-bit shift for bytes 1 & 3
  sum = (sum & 0xff) << 32;
  return (word0 ^ prepost) + sum;
}

// OCTAGRAM wrapper with surrounding spaces
// Pick up 1..24 bytes plus pre/post space and hash them via mask/shift/add
// UNDERSHOOTS 1 byte, OVERSHOOTS up to 3 bytes
//
// The low 32 bits follow the pattern from above, tuned to different scripts
// The high 8 bits are a simple sum of all bytes, shifted by 0/1/2/3 bits each
// For runtime use of tables V3
uint64 cld::OctaHash40(const char* word_ptr, int bytecount) {
  if (bytecount == 0) {
    return 0;
  }
  uint64 prepost = 0;
  if (word_ptr[-1] == ' ') {prepost |= kPreSpaceIndicator;}
  if (word_ptr[bytecount] == ' ') {prepost |= kPostSpaceIndicator;}
  return OctaHash40Mix(word_ptr, bytecount, prepost);
}


// OCTAGRAM wrapper with surrounding underscores (offline use)
// Pick up 1..24 bytes plus pre/post space and hash them via mask/shift/add
// UNDERSHOOTS 1 byte, OVERSHOOTS up to 3 bytes
//
// The low 32 bits follow the pattern from above, tuned to different scripts
// The high 8 bits are a simple sum of all bytes, shifted by 0/1/2/3 bits each
// For offline construction of tables
uint64 cld::OctaHash40underscore(const char* word_ptr, int bytecount) {
  if (bytecount == 0) {
    return 0;
  }
  const char* local_word_ptr = word_ptr;
  int local_bytecount = bytecount;
  uint64 prepost = 0;
  if (local_word_ptr[0] == '_') {
    prepost |= kPreSpaceIndicator;
    ++local_word_ptr;
    --local_bytecount;
  }
  if (local_word_ptr[local_bytecount - 1] == '_') {
    prepost |= kPostSpaceIndicator;
    --local_bytecount;
  }
  return OctaHash40Mix(local_word_ptr, local_bytecount, prepost);
}


//------------------------------------------------------------------------------
// Scoring single groups of letters
//------------------------------------------------------------------------------

// UNIGRAM score one => tote
// Input: 1-byte entry of subscript into unigram probs, plus
//  an accumulator tote.
// Output: running sums in tote updated
void cld::ProcessProbV25UniTote(int propval, Tote* tote) {
  tote->AddGram();
  const UnigramProbArray* pa = &kTargetCTJKVZProbs[propval];
  if (pa->probs[0] > 0) {tote->Add(cld::PackLanguage(CHINESE), pa->probs[0]);}
  if (pa->probs[1] > 0) {tote->Add(cld::PackLanguage(CHINESE_T), pa->probs[1]);}
  if (pa->probs[2] > 0) {tote->Add(cld::PackLanguage(JAPANESE), pa->probs[2]);}
  if (pa->probs[3] > 0) {tote->Add(cld::PackLanguage(KOREAN), pa->probs[3]);}
  if (pa->probs[4] > 0) {tote->Add(cld::PackLanguage(VIETNAMESE), pa->probs[4]);}
  if (pa->probs[5] > 0) {tote->Add(cld::PackLanguage(ZHUANG), pa->probs[5]);}
}

// BIGRAM, QUADGRAM, OCTAGRAM score one => tote
// Input: 4-byte entry of 3 language numbers and one probability subscript, plus
//  an accumulator tote. (language 0 means unused entry)
// Output: running sums in tote updated
void cld::ProcessProbV25Tote(uint32 probs, Tote* tote) {
  tote->AddGram();
  uint8 prob123 = (probs >> 0) & 0xff;
  const uint8* prob123_entry = cld::LgProb2TblEntry(prob123);

  uint8 top1 = (probs >> 8) & 0xff;
  if (top1 > 0) {tote->Add(top1, cld::LgProb3(prob123_entry, 0));}
  uint8 top2 = (probs >> 16) & 0xff;
  if (top2 > 0) {tote->Add(top2, cld::LgProb3(prob123_entry, 1));}
  uint8 top3 = (probs >> 24) & 0xff;
  if (top3 > 0) {tote->Add(top3, cld::LgProb3(prob123_entry, 2));}
}


//------------------------------------------------------------------------------
// Routines to accumulate probabilities
//------------------------------------------------------------------------------


// UNIGRAM, using UTF-8 property table, advancing by 1/2/4/8 chars
// Caller supplies table, such as compact_lang_det_generated_ctjkvz_b1_obj
// Score up to n unigrams, returning number of bytes consumed
// Updates tote_grams
int cld::DoUniScoreV3(const UTF8PropObj* unigram_obj,
                      const char* isrc, int srclen, int advance_by,
                      int* tote_grams, int gram_limit, Tote* chunk_tote) {
  const char* src = isrc;
  if (FLAGS_dbgscore) {DbgScoreInit(src, srclen);}

  // Property-based CJK unigram lookup
  if (src[0] == ' ') {++src; --srclen;}

  const uint8* usrc = reinterpret_cast<const uint8*>(src);
  int usrclen = srclen;

  while (usrclen > 0) {
    int len = kAdvanceOneChar[usrc[0]];
    // Look up property of one UTF-8 character and advance over it
    // Return 0 if input length is zero
    // Return 0 and advance one byte if input is ill-formed

    int propval = UTF8GenericPropertyBigOneByte(unigram_obj, &usrc, &usrclen);

    if (FLAGS_dbglookup) {
      DbgUniTermToStderr(propval, usrc, len);
    }

    if (propval > 0) {
      ProcessProbV25UniTote(propval, chunk_tote);
      ++(*tote_grams);
      if (FLAGS_dbgscore) {DbgScoreRecordUni((const char*)usrc, propval, len);}
    }

    // Advance by 1/2/4/8 characters (half of quad advance)
    if (advance_by == 2) {
      // Already advanced by 1
    } else if (advance_by == 4) {
      // Advance by 2 chars total, if not at end
      if (UTFmax <= usrclen) {
        int n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
      }
    } else if (advance_by == 8) {
      // Advance by 4 chars total, if not at end
      if ((UTFmax * 3) <= usrclen) {
        int n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
      }
    } else {
      // Advance by 8 chars total, if not at end
      if ((UTFmax * 7) <= usrclen) {
        int n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
        n = kAdvanceOneChar[*usrc]; usrc += n; usrclen -= n;
      }
    }
    DCHECK(usrclen >= 0);

    if (*tote_grams >= gram_limit) {
      break;
    }
  }
  if (FLAGS_dbgscore) {
    // With advance_by>2, we consume more input to get the same number of quads
    int len = src - isrc;
    DbgScoreTop(src, (len * 2) / advance_by, chunk_tote);
    DbgScoreFlush();
  }

  int consumed2 = reinterpret_cast<const char*>(usrc) - isrc;
  return consumed2;
}


// BIGRAM, using hash table, always advancing by 1 char
// Caller supplies table, such as &kCjkBiTable_obj or &kGibberishTable_obj
// Score all bigrams in isrc, using languages that have bigrams (CJK)
// Return number of bigrams that hit in the hash table
int cld::DoBigramScoreV3(const cld::CLDTableSummary* bigram_obj,
                         const char* isrc, int srclen, Tote* chunk_tote) {
  int hit_count = 0;
  const char* src = isrc;

  // Hashtable-based CJK bigram lookup
  const uint8* usrc = reinterpret_cast<const uint8*>(src);
  const uint8* usrclimit1 = usrc + srclen - UTFmax;
  if (FLAGS_dbgscore) {
    fprintf(stderr, "  " );
  }

  while (usrc < usrclimit1) {
    int len = kAdvanceOneChar[usrc[0]];
    int len2 = kAdvanceOneChar[usrc[len]] + len;

    if ((kMinCJKUTF8CharBytes * 2) <= len2) {      // Two CJK chars possible
      // Lookup and score this bigram
      // Always ignore pre/post spaces
      uint32 bihash = BiHashV25(reinterpret_cast<const char*>(usrc), len2);
      uint32 probs = QuadHashV3Lookup4(bigram_obj, bihash);
      // Now go indirect on the subscript
      probs = bigram_obj->kCLDTableInd[probs &
        ~bigram_obj->kCLDTableKeyMask];

      // Process the bigram
      if (FLAGS_dbglookup) {
        const char* ssrc = reinterpret_cast<const char*>(usrc);
        DbgBiTermToStderr(bihash, probs, ssrc, len2);
        DbgScoreRecord(NULL, probs, len2);
      } else if (FLAGS_dbgscore && (probs != 0)) {
        const char* ssrc = reinterpret_cast<const char*>(usrc);
        DbgScoreRecord(NULL, probs, len2);
        string temp(ssrc, len2);
        fprintf(stderr, "%s ", temp.c_str());
      }

      if (probs != 0) {
        ProcessProbV25Tote(probs, chunk_tote);
        ++hit_count;
      }
    }
    usrc += len;  // Advance by one char
  }

  if (FLAGS_dbgscore) {
    fprintf(stderr, "[%d bigrams scored]\n", hit_count);
    DbgScoreState();
  }
  return hit_count;
}


// QUADGRAM, using hash table, advancing by 2/4/8/16 chars
// Caller supplies table, such as &kQuadTable_obj or &kGibberishTable_obj
// Score up to n quadgrams, returning number of bytes consumed
// Updates tote_grams
int cld::DoQuadScoreV3(const cld::CLDTableSummary* quadgram_obj,
                       const char* isrc, int srclen, int advance_by,
                       int* tote_grams, int gram_limit, Tote* chunk_tote) {
  const char* src = isrc;
  const char* srclimit = src + srclen;
  // Limit is end, which has extra 20 20 20 00 past len
  const char* srclimit7 = src + srclen - (UTFmax * 7);
  const char* srclimit15 = src + srclen - (UTFmax * 15);

  if (FLAGS_dbgscore) {DbgScoreInit(src, srclen);}

  // Run a little cache of last hits to catch overly-repetitive "text"
  int next_prior = 0;
  uint32 prior_quads[2] = {0, 0};

  // Visit all quadgrams
  if (src[0] == ' ') {++src;}
  while (src < srclimit) {
    // Find one quadgram
    const char* src_end = src;
    src_end += kAdvanceOneCharButSpace[(uint8)src_end[0]];
    src_end += kAdvanceOneCharButSpace[(uint8)src_end[0]];
    const char* src_mid = src_end;
    src_end += kAdvanceOneCharButSpace[(uint8)src_end[0]];
    src_end += kAdvanceOneCharButSpace[(uint8)src_end[0]];
    int len = src_end - src;

    // Lookup and score this quadgram
    uint32 quadhash = QuadHashV25(src, len);
    uint32 probs = QuadHashV3Lookup4(quadgram_obj, quadhash);
    // Now go indirect on the subscript
    probs = quadgram_obj->kCLDTableInd[probs &
      ~quadgram_obj->kCLDTableKeyMask];

    // Process the quadgram
    if (FLAGS_dbglookup) {
      DbgQuadTermToStderr(quadhash, probs, src, len);
    }
    if (probs != 0) {
      // Filter out recent repeats. If this works out, use in the other lookups
      if ((quadhash != prior_quads[0]) && (quadhash != prior_quads[1])) {
        prior_quads[next_prior] = quadhash;
        next_prior = (next_prior + 1) & 1;
        ProcessProbV25Tote(probs, chunk_tote);
        ++(*tote_grams);
        if (FLAGS_dbgscore) {DbgScoreRecord(src, probs, len);}
      }
    }

    // Advance all the way past word if at end-of-word
    if (src_end[0] == ' ') {
      src_mid = src_end;
    }

    // Advance by 2/4/8/16 characters
    if (advance_by == 2) {
      src = src_mid;
    } else if (advance_by == 4) {
      src = src_end;
    } else if (advance_by == 8) {
      // Advance by 8 chars total (4 more), if not at end
      if (src < srclimit7) {
        src_end += kAdvanceOneChar[(uint8)src_end[0]];
        src_end += kAdvanceOneChar[(uint8)src_end[0]];
        src_end += kAdvanceOneChar[(uint8)src_end[0]];
        src_end += kAdvanceOneChar[(uint8)src_end[0]];
      }
      src = src_end;
    } else {
      // Advance by 16 chars total (12 more), if not at end
      if (src < srclimit15) {
        // Advance by ~16 chars by adding 3 * current bytelen
        int fourcharlen = src_end - src;
        src = src_end + (3 * fourcharlen);
        // Advance a bit more if mid-character
        src += kAdvanceOneCharSpaceVowel[(uint8)src[0]];
        src += kAdvanceOneCharSpaceVowel[(uint8)src[0]];
      } else {
        src = src_end;
      }
    }
    DCHECK(src < srclimit);
    src += kAdvanceOneCharSpaceVowel[(uint8)src[0]];

    if (*tote_grams >= gram_limit) {
      break;
    }
  }

  if (FLAGS_dbgscore) {
    // With advance_by>2, we consume more input to get the same number of quads
    int len = src - isrc;
    DbgScoreTop(src, (len * 2) / advance_by, chunk_tote);
    DbgScoreFlush();
  }

  int consumed = src - isrc;

  // If advancing by more than 2, src may have overshot srclimit
  if (consumed > srclen) {
    consumed = srclen;
  }

  return consumed;
}


// OCTAGRAM, using hash table, always advancing by 1 word
// Caller supplies table, such as &kLongWord8Table_obj
// Score all words in isrc, using languages that have quadgrams
// We don't normally use this routine except on the first quadgram run,
// but it can be used to resolve unreliable pages.
// This routine does not have an optimized advance_by
// SOON: Uses indirect language/probability longword
//
// Return number of words that hit in the hash table
int cld::DoOctaScoreV3(const cld::CLDTableSummary* octagram_obj,
                       const char* isrc, int srclen, Tote* chunk_tote) {
  int hit_count = 0;
  const char* src = isrc;
  const char* srclimit = src + srclen + 1;
  // Limit is end+1, to include extra space char (0x20) off the end
  //
  // Score all words truncated to 8 characters
  int charcount = 0;
  // Skip any initial space
  if (src[0] == ' ') {++src;}
  const char* word_ptr = src;
  const char* word_end = word_ptr;
  if (FLAGS_dbgscore) {
    fprintf(stderr, "  " );
  }
  while (src < srclimit) {
    // Terminate previous word or continue current word
    if (src[0] == ' ') {
      int bytecount = word_end - word_ptr;
      if (bytecount == 0)
        break;
      // Lookup and score this word
      uint64 wordhash40 = OctaHash40(word_ptr, bytecount);
      uint32 probs = OctaHashV3Lookup4(octagram_obj, wordhash40);
      // Now go indirect on the subscript
      probs = octagram_obj->kCLDTableInd[probs &
        ~octagram_obj->kCLDTableKeyMask];

      // // Lookup and score this word
      // uint32 wordhash = QuadHashV25(word_ptr, bytecount);
      // uint32 probs = WordHashLookup4(wordhash, kLongWord8Table,
      //                                kLongWord8TableSize);
      //
      if (FLAGS_dbglookup) {
        DbgWordTermToStderr(wordhash40, probs, word_ptr, bytecount);
        DbgScoreRecord(NULL, probs, bytecount);
      } else if (FLAGS_dbgscore && (probs != 0)) {
        DbgScoreRecord(NULL, probs, bytecount);
        string temp(word_ptr, bytecount);
        fprintf(stderr, "%s ", temp.c_str());
      }

      if (probs != 0) {
        ProcessProbV25Tote(probs, chunk_tote);
        ++hit_count;
      }
      charcount = 0;
      word_ptr = src + 1;   // Over the space
      word_end = word_ptr;
    } else {
      ++charcount;
    }

    // Advance to next char
    src += cld_UniLib::OneCharLen(src);
    if (charcount <= 8) {
      word_end = src;
    }
  }

  if (FLAGS_dbgscore) {
    fprintf(stderr, "[%d words scored]\n", hit_count);
    DbgScoreState();
  }
  return hit_count;
}


//------------------------------------------------------------------------------
// Reliability calculations, for single language and between languages
//------------------------------------------------------------------------------

// Return reliablity of result 0..100 for top two scores
// delta==0 is 0% reliable, delta==fully_reliable_thresh is 100% reliable
// (on a scale where +1 is a factor of  2 ** 1.6 = 3.02)
// Threshold is uni/quadgram increment count, bounded above and below.
//
// Requiring a factor of 3 improvement (e.g. +1 log base 3)
// for each scored quadgram is too stringent, so I've backed this off to a
// factor of 2 (e.g. +5/8 log base 3).
//
// I also somewhat lowered the Min/MaxGramCount limits above
//
// Added: if fewer than 8 quads/unis, max reliability is 12*n percent
//
int cld::ReliabilityDelta(int value1, int value2, int gramcount) {
  int max_reliability_percent = 100;
  if (gramcount < 8) {
    max_reliability_percent = 12 * gramcount;
  }
  int fully_reliable_thresh = (gramcount * 5) >> 3;     // see note above
  if (fully_reliable_thresh < kMinGramCount) {          // Fully = 3..16
    fully_reliable_thresh = kMinGramCount;
  } else if (fully_reliable_thresh > kMaxGramCount) {
    fully_reliable_thresh = kMaxGramCount;
  }

  int delta = value1 - value2;
  if (delta >= fully_reliable_thresh) {return max_reliability_percent;}
  if (delta <= 0) {return 0;}
  return cld::minint(max_reliability_percent,
                     (100 * delta) / fully_reliable_thresh);
}

// Return reliablity of result 0..100 for top score vs. mainsteam score
// Values are score per 1024 bytes of input
// ratio = max(top/mainstream, mainstream/top)
// ratio > 4.0 is 0% reliable, <= 2.0 is 100% reliable
// Change: short-text word scoring can give unusually good results.
//  Let top exceed mainstream by 4x at 50% reliable
int cld::ReliabilityMainstream(int topscore, int len, int mean_score) {
  if (mean_score == 0) {return 100;}    // No reliability data available yet
  if (topscore == 0) {return 0;}        // zero score = unreliable
  if (len == 0) {return 0;}             // zero len = unreliable
  int top_kb = (topscore << 10) / len;
  double ratio;
  double ratio_cutoff;
  if (top_kb > mean_score) {
    ratio = (1.0 * top_kb) / mean_score;
    ratio_cutoff = 5.0;                 // ramp down from 100% to 0%: 3.0-5.0
  } else {
    ratio = (1.0 * mean_score) / top_kb;
    ratio_cutoff = 4.0;                 // ramp down from 100% to 0%: 2.0-4.0
  }
  if (ratio <= ratio_cutoff - 2.0) {return 100;}
  if (ratio > ratio_cutoff) {return 0;}

  int iratio = static_cast<int>(100 * (ratio_cutoff - ratio) / 2.0);
  return iratio;
}

// Calculate ratio of score per 1KB vs. expected score per 1KB
double cld::GetNormalizedScore(Language lang, UnicodeLScript lscript,
                          int bytes, int score) {
  // Average training-data score for this language-script combo, per 1KB
  int expected_score = kMeanScore[lang * 4 + LScript4(lscript)];
  if (lscript == ULScript_Common) {
    // We don't know the script (only happens with second-chance score)
    // Look for first non-zero mean value
    for (int i = 2; i >= 0; --i) {
      if (kMeanScore[lang * 4 + i] > 0) {
        expected_score = kMeanScore[lang * 4 + i];
        break;
      }
    }
  }
  if (expected_score < 100) {
      expected_score = 1000;
  }

  // Our score per 1KB
  double our_score = (score << 10) / (bytes ? bytes : 1);  // Avoid zdiv
  double ratio = our_score / expected_score;

  // Just the raw count normalized as though each language has mean=1000;
  ratio = (score * 1000.0) /  expected_score;
  return ratio;
}

// Calculate reliablity of len bytes of script lscript with chunk_tote
int cld::GetReliability(int len, UnicodeLScript lscript,
                   const Tote* chunk_tote) {
  Language cur_lang = UnpackLanguage(chunk_tote->Key(0));
  // Average score for this language-script combo
  int mean_score = kMeanScore[cur_lang * 4 + LScript4(lscript)];
  if (lscript == ULScript_Common) {
    // We don't know the script (only happens with second-chance score)
    // Look for first non-zero mean value
    for (int i = 2; i >= 0; --i) {
      if (kMeanScore[cur_lang * 4 + i] > 0) {
        mean_score = kMeanScore[cur_lang * 4 + i];
        break;
      }
    }
  }
  int reliability_delta = ReliabilityDelta(chunk_tote->Value(0),
                                           chunk_tote->Value(1),
                                           chunk_tote->GetGramCount());

  int reliability_main = ReliabilityMainstream(chunk_tote->Value(0),
                                               len,
                                               mean_score);

  int reliability_min = minint(reliability_delta, reliability_main);


  if (FLAGS_dbgreli) {
    char temp1[4];
    char temp2[4];
    cld::DbgLangName3(UnpackLanguage(chunk_tote->Key(0)), temp1);
    if (temp1[2] == ' ') {temp1[2] = '\0';}
    cld::DbgLangName3(UnpackLanguage(chunk_tote->Key(1)), temp2);
    if (temp2[2] == ' ') {temp2[2] = '\0';}
    int srclen = len;
    fprintf(stderr, "CALC GetReliability gram=%d incr=%d srclen=%d,  %s=%d %s=%d "
                   "top/KB=%d mean/KB=%d del=%d%% reli=%d%%   "
                   "lang/lscript %d %d\n",
           chunk_tote->GetGramCount(),
           chunk_tote->GetIncrCount(),
           srclen,
           temp1, chunk_tote->Value(0),
           temp2, chunk_tote->Value(1),
           (chunk_tote->Value(0) << 10) / (srclen ? srclen : 1),
           mean_score,
           reliability_delta,
           reliability_main,
           cur_lang, lscript);
  }

  return reliability_min;
}


//------------------------------------------------------------------------------
// Miscellaneous
//------------------------------------------------------------------------------

// Demote all languages except Top40 and plus_one
// Do this just before sorting chunk_tote results
void cld::DemoteNotTop40(Tote* chunk_tote, int packed_plus_one) {
  for (int sub = 0; sub < chunk_tote->MaxSize(); ++sub) {
    if (chunk_tote->Key(sub) == 0) continue;
    if (chunk_tote->Key(sub) == packed_plus_one) continue;
    if (kIsPackedTop40[chunk_tote->Key(sub)]) continue;
    // Quarter the score of others
    chunk_tote->SetValue(sub, chunk_tote->Value(sub) >> 2);
  }
}