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)

 //

 //

 // Terminology:

 // Incoming original text has HTML tags and entities removed, all but letters

 // removed, and letters lowercased. Strings of non-letters are mapped to a

 // single ASCII space.

 //

 // One scriptspan has a run of letters/spaces  in a single script. This is the

 // fundamental text unit that is scored. There is an optional backmap from

 // scriptspan text to the original document text, so that the language ranges

 // reported in ResultChunkVector refer to byte ranges inthe original text.

 //

 // Scripts come in two forms, the full Unicode scripts described by

 //   http://www.unicode.org/Public/UNIDATA/Scripts.txt

 // and a modified list used exclusively in CLD2. The modified form maps all

 // the CJK scripts to one, Hani. The current version description is in

 //  i18n/encodings/cld2/builddata/script_summary.txt

 // In addition, all non-letters are mapped to the Common script.

 //

 // ULScript describes this Unicode Letter script.

 //

 // Scoring uses text nil-grams, uni-grams, bi-grams, quad-grams, and octa-grams.

 // Nilgrams (no text lookup at all) are for script-based pseudo-languages and

 // for languages that are 1:1 with a given script. Unigrams and bigrams are

 // used to score the CJK languages, all in the Hani script. Quadgrams and

 // octagrams are used to score all other languages.

 //

 // RType is the Recognition Type per ulscript.

 //

 // The scoring tables map various grams to language-probability scores.

 // A given gram that hits in scoring table maps to an indirect subscript into

 // a list of packed languages and log probabilities.

 //

 // Languages are stored in two forms: 10-bit values in the Languge enum, and

 // shorter 8-bit per-ulscript values in the scoring tables.

 //

 // Language refers to the full 10-bit range.

 // pslang refers to the per-ulscript shorter values.

 //

 // Log probabilities also come in two forms. The full range uses values 0..255

 // to represent minus log base 10th-root-of-2, covering 1 .. 1/2**25.5 or about

 // TODO BOGUS description, 24 vs 12

 // 1/47.5M. The second form quantizes these into multiples of 8 that can be

 // added together to represent probability products. The quantized form uses

 // values 24..0 with 0 now least likely instead of most likely, thus making

 // larger sums for more probable results. 24 maps to original 1/2**4.8 (~1/28)

 // and 0 maps to original 1/2**24.0 (~1/16M).

 //

 // qprob refers to quantized log probabilities.

 //

 // langprob is a uint32 holding three 1-byte pslangs and a 1-byte subscript to

 // a list of three qprobs. It always nees a companion ulscript

 //

 // A scriptspan is scored via one or more hitbuffers

 #ifndef I18N_ENCODINGS_CLD2_INTERNAL_SCOREONESCRIPTSPAN_H__

 #define I18N_ENCODINGS_CLD2_INTERNAL_SCOREONESCRIPTSPAN_H__

 #include <stdio.h>

 #include "integral_types.h"           // for uint8 etc.

 #include "cld2tablesummary.h"

 #include "compact_lang_det_impl.h"    // for ResultChunkVector

 #include "getonescriptspan.h"

 #include "langspan.h"

 #include "tote.h"

 #include "utf8statetable.h"

 namespace CLD2 {

 static const int kMaxBoosts = 4;              // For each of PerScriptLangBoosts

                                               // must be power of two for wrap()

 static const int kChunksizeQuads = 20;        // For non-CJK

 static const int kChunksizeUnis = 50;         // For CJK

 static const int kMaxScoringHits = 1000;

 static const int kMaxSummaries = kMaxScoringHits / kChunksizeQuads;

 // The first four tables are for CJK languages,

 // the next three for quadgram languages, and

 // the last for expected scores.

 typedef struct {

   const UTF8PropObj* unigram_obj;               // 80K CJK characters

   const CLD2TableSummary* unigram_compat_obj;   // 256 CJK lookup probabilities

   const CLD2TableSummary* deltabi_obj;

   const CLD2TableSummary* distinctbi_obj;

   const CLD2TableSummary* quadgram_obj;         // Primary quadgram lookup table

   const CLD2TableSummary* quadgram_obj2;        // Secondary  "

   const CLD2TableSummary* deltaocta_obj;

   const CLD2TableSummary* distinctocta_obj;

   const short* kExpectedScore;      // Expected base + delta + distinct score

                                     // per 1KB input

                                     // Subscripted by language and script4

 } ScoringTables;

 // Context for boosting several languages

 typedef struct {

    int32 n;

    uint32 langprob[kMaxBoosts];

    int wrap(int32 n) {return n & (kMaxBoosts - 1);}

 } LangBoosts;

 typedef struct {

    LangBoosts latn;

    LangBoosts othr;

 } PerScriptLangBoosts;

 // ScoringContext carries state across scriptspans

 // ScoringContext also has read-only scoring tables mapping grams to qprobs

 typedef struct {

   FILE* debug_file;                   // Non-NULL if debug output wanted

   bool flags_cld2_score_as_quads;

   bool flags_cld2_html;

   bool flags_cld2_cr;

   bool flags_cld2_verbose;

   ULScript ulscript;        // langprobs below are with respect to this script

   Language prior_chunk_lang;          // Mostly for debug output

   // boost has a packed set of per-script langs and probabilites

   // whack has a per-script lang to be suppressed from ever scoring (zeroed)

   // When a language in a close set is given as an explicit hint, others in

   //  that set will be whacked.

   PerScriptLangBoosts langprior_boost;  // From http content-lang or meta lang=

   PerScriptLangBoosts langprior_whack;  // From http content-lang or meta lang=

   PerScriptLangBoosts distinct_boost;   // From distinctive letter groups

   int oldest_distinct_boost;          // Subscript in hitbuffer of oldest

                                       // distinct score to use

   const ScoringTables* scoringtables; // Probability lookup tables

   ScriptScanner* scanner;             // For ResultChunkVector backmap

   // Inits boosts

   void init() {

     memset(&langprior_boost, 0, sizeof(langprior_boost));

     memset(&langprior_whack, 0, sizeof(langprior_whack));

     memset(&distinct_boost, 0, sizeof(distinct_boost));

   };

 } ScoringContext;

 // Begin private

 // Holds one scoring-table lookup hit. We hold indirect subscript instead of

 // langprob to allow a single hit to use a variable number of langprobs.

 typedef struct {

   int offset;         // First byte of quad/octa etc. in scriptspan

   int indirect;       // subscript of langprobs in scoring table

 } ScoringHit;

 typedef enum {

   UNIHIT                       = 0,

   QUADHIT                      = 1,

   DELTAHIT                     = 2,

   DISTINCTHIT                  = 3

 } LinearHitType;

 // Holds one scoring-table lookup hit resolved into a langprob.

 typedef struct {

   uint16 offset;      // First byte of quad/octa etc. in scriptspan

   uint16 type;        // LinearHitType

   uint32 langprob;    // langprob from scoring table

 } LangprobHit;

 // Holds arrays of scoring-table lookup hits for (part of) a scriptspan

 typedef struct {

   ULScript ulscript;        // langprobs below are with respect to this script

   int maxscoringhits;       // determines size of arrays below

   int next_base;            // First unused entry in each array

   int next_delta;           //   "

   int next_distinct;        //   "

   int next_linear;          //   "

   int next_chunk_start;     // First unused chunk_start entry

   int lowest_offset;        // First byte of text span used to fill hitbuffer

   // Dummy entry at the end of each giving offset of first unused text byte

   ScoringHit base[kMaxScoringHits + 1];         // Uni/quad hits

   ScoringHit delta[kMaxScoringHits + 1];        // delta-bi/delta-octa hits

   ScoringHit distinct[kMaxScoringHits + 1];     // distinct-word hits

   LangprobHit linear[4 * kMaxScoringHits + 1];  // Above three merge-sorted

                                                 // (4: some bases => 2 linear)

   int chunk_start[kMaxSummaries + 1];           // First linear[] subscr of

                                                 //  each scored chunk

   int chunk_offset[kMaxSummaries + 1];          // First text subscr of

                                                 //  each scored chunk

   void init() {

     ulscript = ULScript_Common;

     maxscoringhits = kMaxScoringHits;

     next_base = 0;

     next_delta = 0;

     next_distinct = 0;

     next_linear = 0;

     next_chunk_start = 0;

     lowest_offset = 0;

     base[0].offset = 0;

     base[0].indirect = 0;

     delta[0].offset = 0;

     delta[0].indirect = 0;

     distinct[0].offset = 0;

     distinct[0].indirect = 0;

     linear[0].offset = 0;

     linear[0].langprob = 0;

     chunk_start[0] = 0;

     chunk_offset[0] = 0;

   };

 } ScoringHitBuffer;

 // TODO: Explain here why we need both ChunkSpan and ChunkSummary

 typedef struct {

   int chunk_base;       // Subscript of first hitbuffer.base[] in chunk

   int chunk_delta;      // Subscript of first hitbuffer.delta[]

   int chunk_distinct;   // Subscript of first hitbuffer.distinct[]

   int base_len;         // Number of hitbuffer.base[] in chunk

   int delta_len;        // Number of hitbuffer.delta[] in chunk

   int distinct_len;     // Number of hitbuffer.distinct[] in chunk

 } ChunkSpan;

 // Packed into 20 bytes for space

 typedef struct {

   uint16 offset;              // Text offset within current scriptspan.text

   uint16 chunk_start;         // Scoring subscr within hitbuffer->linear[]

   uint16 lang1;               // Top lang, mapped to full Language

   uint16 lang2;               // Second lang, mapped to full Language

   uint16 score1;              // Top lang raw score

   uint16 score2;              // Second lang raw score

   uint16 bytes;               // Number of lower letters bytes in chunk

   uint16 grams;               // Number of scored base quad- uni-grams in chunk

   uint16 ulscript;            // ULScript of chunk

   uint8 reliability_delta;    // Reliability 0..100, delta top:second scores

   uint8 reliability_score;    // Reliability 0..100, top:expected score

 } ChunkSummary;

 // We buffer up ~50 chunk summaries, corresponding to chunks of 20 quads in a

 // 1000-quad hit buffer, so we can do boundary adjustment on them

 // when adjacent entries are different languages. After that, we add them

 // all into the document score

 //

 // About 50 * 20 = 1000 bytes. OK for stack alloc

 typedef struct {

   int n;

   ChunkSummary chunksummary[kMaxSummaries + 1];

 } SummaryBuffer;

 // End private

 // Score RTypeNone or RTypeOne scriptspan into doc_tote and vec, updating

 // scoringcontext

 void ScoreEntireScriptSpan(const LangSpan& scriptspan,

                            ScoringContext* scoringcontext,

                            DocTote* doc_tote,

                            ResultChunkVector* vec);

 // Score RTypeCJK scriptspan into doc_tote and vec, updating scoringcontext

 void ScoreCJKScriptSpan(const LangSpan& scriptspan,

                         ScoringContext* scoringcontext,

                         DocTote* doc_tote,

                         ResultChunkVector* vec);

 // Score RTypeMany scriptspan into doc_tote and vec, updating scoringcontext

 void ScoreQuadScriptSpan(const LangSpan& scriptspan,

                          ScoringContext* scoringcontext,

                          DocTote* doc_tote,

                          ResultChunkVector* vec);

 // Score one scriptspan into doc_tote and vec, updating scoringcontext

 void ScoreOneScriptSpan(const LangSpan& scriptspan,

                         ScoringContext* scoringcontext,

                         DocTote* doc_tote,

                         ResultChunkVector* vec);

 }       // End namespace CLD2

 #endif  // I18N_ENCODINGS_CLD2_INTERNAL_SCOREONESCRIPTSPAN_H__