1 // Copyright 2013 Google Inc. All Rights Reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 // 15 // Class to model the static dictionary. 16 17 #ifndef BROTLI_ENC_STATIC_DICT_H_ 18 #define BROTLI_ENC_STATIC_DICT_H_ 19 20 #include <algorithm> 21 #include <unordered_map> 22 #include <string> 23 24 namespace brotli { 25 26 class StaticDictionary { 27 public: StaticDictionary()28 StaticDictionary() {} Insert(const std::string & str,int len,int dist)29 void Insert(const std::string &str, int len, int dist) { 30 int ix = (dist << 6) + len; 31 std::unordered_map<std::string, int>::const_iterator it = map_.find(str); 32 if (it != map_.end() && ix >= it->second) { 33 return; 34 } 35 map_[str] = ix; 36 int v = 0; 37 for (int i = 0; i < 4 && i < str.size(); ++i) { 38 v += str[i] << (8 * i); 39 } 40 if (prefix_map_[v] < str.size()) { 41 prefix_map_[v] = str.size(); 42 } 43 } GetLength(int v)44 int GetLength(int v) const { 45 std::unordered_map<int, int>::const_iterator it = prefix_map_.find(v); 46 if (it == prefix_map_.end()) { 47 return 0; 48 } 49 return it->second; 50 } Get(const std::string & str,int * len,int * dist)51 bool Get(const std::string &str, int *len, int *dist) const { 52 std::unordered_map<std::string, int>::const_iterator it = map_.find(str); 53 if (it == map_.end()) { 54 return false; 55 } 56 int v = it->second; 57 *len = v & 63; 58 *dist = v >> 6; 59 return true; 60 } 61 private: 62 std::unordered_map<std::string, int> map_; 63 std::unordered_map<int, int> prefix_map_; 64 }; 65 66 } // namespace brotli 67 68 #endif // BROTLI_ENC_STATIC_DICT_H_ 69