net/base/lookup_string_in_fixed_set.cc

// Copyright 2015 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 "net/base/lookup_string_in_fixed_set.h"

#include "base/logging.h"

namespace net {

namespace {

// Read next offset from pos.
// Returns true if an offset could be read, false otherwise.
bool GetNextOffset(const unsigned char** pos,
                   const unsigned char* end,
                   const unsigned char** offset) {
  if (*pos == end)
    return false;

  // When reading an offset the byte array must always contain at least
  // three more bytes to consume. First the offset to read, then a node
  // to skip over and finally a destination node. No object can be smaller
  // than one byte.
  CHECK_LT(*pos + 2, end);
  size_t bytes_consumed;
  switch (**pos & 0x60) {
    case 0x60:  // Read three byte offset
      *offset += (((*pos)[0] & 0x1F) << 16) | ((*pos)[1] << 8) | (*pos)[2];
      bytes_consumed = 3;
      break;
    case 0x40:  // Read two byte offset
      *offset += (((*pos)[0] & 0x1F) << 8) | (*pos)[1];
      bytes_consumed = 2;
      break;
    default:
      *offset += (*pos)[0] & 0x3F;
      bytes_consumed = 1;
  }
  if ((**pos & 0x80) != 0) {
    *pos = end;
  } else {
    *pos += bytes_consumed;
  }
  return true;
}

// Check if byte at offset is last in label.
bool IsEOL(const unsigned char* offset, const unsigned char* end) {
  CHECK_LT(offset, end);
  return (*offset & 0x80) != 0;
}

// Check if byte at offset matches first character in key.
// This version matches characters not last in label.
bool IsMatch(const unsigned char* offset,
             const unsigned char* end,
             const char* key) {
  CHECK_LT(offset, end);
  return *offset == *key;
}

// Check if byte at offset matches first character in key.
// This version matches characters last in label.
bool IsEndCharMatch(const unsigned char* offset,
                    const unsigned char* end,
                    const char* key) {
  CHECK_LT(offset, end);
  return *offset == (*key | 0x80);
}

// Read return value at offset.
// Returns true if a return value could be read, false otherwise.
bool GetReturnValue(const unsigned char* offset,
                    const unsigned char* end,
                    int* return_value) {
  CHECK_LT(offset, end);
  if ((*offset & 0xE0) == 0x80) {
    *return_value = *offset & 0x0F;
    return true;
  }
  return false;
}

}  // namespace

// Lookup a domain key in a byte array generated by make_dafsa.py.
// The rule type is returned if key is found, otherwise kDafsaNotFound is
// returned.
int LookupStringInFixedSet(const unsigned char* graph,
                           size_t length,
                           const char* key,
                           size_t key_length) {
  const unsigned char* pos = graph;
  const unsigned char* end = graph + length;
  const unsigned char* offset = pos;
  const char* key_end = key + key_length;
  while (GetNextOffset(&pos, end, &offset)) {
    //   char <char>+ end_char offsets
    //   char <char>+ return value
    //   char end_char offsets
    //   char return value
    //   end_char offsets
    //   return_value
    bool did_consume = false;
    if (key != key_end && !IsEOL(offset, end)) {
      // Leading <char> is not a match. Don't dive into this child
      if (!IsMatch(offset, end, key))
        continue;
      did_consume = true;
      ++offset;
      ++key;
      // Possible matches at this point:
      // <char>+ end_char offsets
      // <char>+ return value
      // end_char offsets
      // return value
      // Remove all remaining <char> nodes possible
      while (!IsEOL(offset, end) && key != key_end) {
        if (!IsMatch(offset, end, key))
          return kDafsaNotFound;
        ++key;
        ++offset;
      }
    }
    // Possible matches at this point:
    // end_char offsets
    // return_value
    // If one or more <char> elements were consumed, a failure
    // to match is terminal. Otherwise, try the next node.
    if (key == key_end) {
      int return_value;
      if (GetReturnValue(offset, end, &return_value))
        return return_value;
      // The DAFSA guarantees that if the first char is a match, all
      // remaining char elements MUST match if the key is truly present.
      if (did_consume)
        return kDafsaNotFound;
      continue;
    }
    if (!IsEndCharMatch(offset, end, key)) {
      if (did_consume)
        return kDafsaNotFound;  // Unexpected
      continue;
    }
    ++key;
    pos = ++offset;  // Dive into child
  }
  return kDafsaNotFound;  // No match
}

}  // namespace net