xpcom/ds/Dafsa.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
   8 // Use of this source code is governed by a BSD-style license that can be
   9 // found in the LICENSE file.
  10
  11 #include "Dafsa.h"
  12
  13 #include "mozilla/Assertions.h"
  14 #include "nsAString.h"
  15
  16 const int mozilla::Dafsa::kKeyNotFound = -1;
  17
  18 // Note the DAFSA implementation was lifted from eTLD code in Chromium that was
  19 // originally lifted from Firefox.
  20
  21 // Read next offset from pos.
  22 // Returns true if an offset could be read, false otherwise.
  23 static bool GetNextOffset(const unsigned char** pos, const unsigned char* end,
  24                           const unsigned char** offset) {
  25   if (*pos == end) return false;
  26
  27   // When reading an offset the byte array must always contain at least
  28   // three more bytes to consume. First the offset to read, then a node
  29   // to skip over and finally a destination node. No object can be smaller
  30   // than one byte.
  31   MOZ_ASSERT(*pos + 2 < end);
  32   size_t bytes_consumed;
  33   switch (**pos & 0x60) {
  34     case 0x60:  // Read three byte offset
  35       *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
  36       bytes_consumed = 3;
  37       break;
  38     case 0x40:  // Read two byte offset
  39       *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
  40       bytes_consumed = 2;
  41       break;
  42     default:
  43       *offset += (*pos)[0] & 0x3F;
  44       bytes_consumed = 1;
  45   }
  46   if ((**pos & 0x80) != 0) {
  47     *pos = end;
  48   } else {
  49     *pos += bytes_consumed;
  50   }
  51   return true;
  52 }
  53
  54 // Check if byte at offset is last in label.
  55 static bool IsEOL(const unsigned char* offset, const unsigned char* end) {
  56   MOZ_ASSERT(offset < end);
  57   return (*offset & 0x80) != 0;
  58 }
  59
  60 // Check if byte at offset matches first character in key.
  61 // This version matches characters not last in label.
  62 static bool IsMatch(const unsigned char* offset, const unsigned char* end,
  63                     const char* key) {
  64   MOZ_ASSERT(offset < end);
  65   return *offset == *key;
  66 }
  67
  68 // Check if byte at offset matches first character in key.
  69 // This version matches characters last in label.
  70 static bool IsEndCharMatch(const unsigned char* offset,
  71                            const unsigned char* end, const char* key) {
  72   MOZ_ASSERT(offset < end);
  73   return *offset == (*key | 0x80);
  74 }
  75
  76 // Read return value at offset.
  77 // Returns true if a return value could be read, false otherwise.
  78 static bool GetReturnValue(const unsigned char* offset,
  79                            const unsigned char* end, int* return_value) {
  80   MOZ_ASSERT(offset < end);
  81   if ((*offset & 0xE0) == 0x80) {
  82     *return_value = *offset & 0x0F;
  83     return true;
  84   }
  85   return false;
  86 }
  87
  88 // Lookup a domain key in a byte array generated by make_dafsa.py.
  89 // The rule type is returned if key is found, otherwise kKeyNotFound is
  90 // returned.
  91 static int LookupString(const unsigned char* graph, size_t length,
  92                         const char* key, size_t key_length) {
  93   const unsigned char* pos = graph;
  94   const unsigned char* end = graph + length;
  95   const unsigned char* offset = pos;
  96   const char* key_end = key + key_length;
  97   while (GetNextOffset(&pos, end, &offset)) {
  98     //   char <char>+ end_char offsets
  99     //   char <char>+ return value
 100     //   char end_char offsets
 101     //   char return value
 102     //   end_char offsets
 103     //   return_value
 104     bool did_consume = false;
 105     if (key != key_end && !IsEOL(offset, end)) {
 106       // Leading <char> is not a match. Don't dive into this child
 107       if (!IsMatch(offset, end, key)) continue;
 108       did_consume = true;
 109       ++offset;
 110       ++key;
 111       // Possible matches at this point:
 112       // <char>+ end_char offsets
 113       // <char>+ return value
 114       // end_char offsets
 115       // return value
 116       // Remove all remaining <char> nodes possible
 117       while (!IsEOL(offset, end) && key != key_end) {
 118         if (!IsMatch(offset, end, key)) return mozilla::Dafsa::kKeyNotFound;
 119         ++key;
 120         ++offset;
 121       }
 122     }
 123     // Possible matches at this point:
 124     // end_char offsets
 125     // return_value
 126     // If one or more <char> elements were consumed, a failure
 127     // to match is terminal. Otherwise, try the next node.
 128     if (key == key_end) {
 129       int return_value;
 130       if (GetReturnValue(offset, end, &return_value)) return return_value;
 131       // The DAFSA guarantees that if the first char is a match, all
 132       // remaining char elements MUST match if the key is truly present.
 133       if (did_consume) return mozilla::Dafsa::kKeyNotFound;
 134       continue;
 135     }
 136     if (!IsEndCharMatch(offset, end, key)) {
 137       if (did_consume) return mozilla::Dafsa::kKeyNotFound;  // Unexpected
 138       continue;
 139     }
 140     ++key;
 141     pos = ++offset;  // Dive into child
 142   }
 143   return mozilla::Dafsa::kKeyNotFound;  // No match
 144 }
 145
 146 namespace mozilla {
 147
 148 int Dafsa::Lookup(const nsACString& aKey) const {
 149   return LookupString(mData.Elements(), mData.Length(), aKey.BeginReading(),
 150                       aKey.Length());
 151 }
 152
 153 }  // namespace mozilla