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