unique_position.cc 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595
  1. // Copyright (c) 2012 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. #include "components/sync/base/unique_position.h"
  5. #include <algorithm>
  6. #include <limits>
  7. #include "base/logging.h"
  8. #include "base/rand_util.h"
  9. #include "base/strings/string_number_conversions.h"
  10. #include "base/trace_event/memory_usage_estimator.h"
  11. #include "components/sync/protocol/unique_position.pb.h"
  12. #include "third_party/zlib/zlib.h"
  13. namespace syncer {
  14. constexpr size_t UniquePosition::kSuffixLength;
  15. constexpr size_t UniquePosition::kCompressBytesThreshold;
  16. // static.
  17. bool UniquePosition::IsValidSuffix(const std::string& suffix) {
  18. // The suffix must be exactly the specified length, otherwise unique suffixes
  19. // are not sufficient to guarantee unique positions (because prefix + suffix
  20. // == p + refixsuffix).
  21. return suffix.length() == kSuffixLength && suffix[kSuffixLength - 1] != 0;
  22. }
  23. // static.
  24. bool UniquePosition::IsValidBytes(const std::string& bytes) {
  25. // The first condition ensures that our suffix uniqueness is sufficient to
  26. // guarantee position uniqueness. Otherwise, it's possible the end of some
  27. // prefix + some short suffix == some long suffix.
  28. // The second condition ensures that FindSmallerWithSuffix can always return a
  29. // result.
  30. return bytes.length() >= kSuffixLength && bytes[bytes.length() - 1] != 0;
  31. }
  32. // static.
  33. std::string UniquePosition::RandomSuffix() {
  34. // Users random data for all but the last byte. The last byte must not be
  35. // zero. We arbitrarily set it to 0x7f.
  36. return base::RandBytesAsString(kSuffixLength - 1) + "\x7f";
  37. }
  38. // static.
  39. UniquePosition UniquePosition::FromProto(const sync_pb::UniquePosition& proto) {
  40. if (proto.has_custom_compressed_v1()) {
  41. return UniquePosition(proto.custom_compressed_v1());
  42. } else if (proto.has_value() && !proto.value().empty()) {
  43. return UniquePosition(Compress(proto.value()));
  44. } else if (proto.has_compressed_value() && proto.has_uncompressed_length()) {
  45. uLongf uncompressed_len = proto.uncompressed_length();
  46. std::string un_gzipped;
  47. un_gzipped.resize(uncompressed_len);
  48. int result = uncompress(
  49. reinterpret_cast<Bytef*>(std::data(un_gzipped)), &uncompressed_len,
  50. reinterpret_cast<const Bytef*>(proto.compressed_value().data()),
  51. proto.compressed_value().size());
  52. if (result != Z_OK) {
  53. DLOG(ERROR) << "Unzip failed " << result;
  54. return UniquePosition();
  55. }
  56. if (uncompressed_len != proto.uncompressed_length()) {
  57. DLOG(ERROR) << "Uncompressed length " << uncompressed_len
  58. << " did not match specified length "
  59. << proto.uncompressed_length();
  60. return UniquePosition();
  61. }
  62. return UniquePosition(Compress(un_gzipped));
  63. } else {
  64. return UniquePosition();
  65. }
  66. }
  67. // static.
  68. UniquePosition UniquePosition::FromInt64(int64_t x, const std::string& suffix) {
  69. uint64_t y = static_cast<uint64_t>(x);
  70. y ^= 0x8000000000000000ULL; // Make it non-negative.
  71. std::string bytes(8, 0);
  72. for (int i = 7; i >= 0; --i) {
  73. bytes[i] = static_cast<uint8_t>(y);
  74. y >>= 8;
  75. }
  76. return UniquePosition(bytes + suffix, suffix);
  77. }
  78. // static.
  79. UniquePosition UniquePosition::InitialPosition(const std::string& suffix) {
  80. DCHECK(IsValidSuffix(suffix));
  81. return UniquePosition(suffix, suffix);
  82. }
  83. // static.
  84. UniquePosition UniquePosition::Before(const UniquePosition& x,
  85. const std::string& suffix) {
  86. DCHECK(IsValidSuffix(suffix));
  87. DCHECK(x.IsValid());
  88. const std::string& before =
  89. FindSmallerWithSuffix(Uncompress(x.compressed_), suffix);
  90. return UniquePosition(before + suffix, suffix);
  91. }
  92. // static.
  93. UniquePosition UniquePosition::After(const UniquePosition& x,
  94. const std::string& suffix) {
  95. DCHECK(IsValidSuffix(suffix));
  96. DCHECK(x.IsValid());
  97. const std::string& after =
  98. FindGreaterWithSuffix(Uncompress(x.compressed_), suffix);
  99. return UniquePosition(after + suffix, suffix);
  100. }
  101. // static.
  102. UniquePosition UniquePosition::Between(const UniquePosition& before,
  103. const UniquePosition& after,
  104. const std::string& suffix) {
  105. DCHECK(before.IsValid());
  106. DCHECK(after.IsValid());
  107. DCHECK(before.LessThan(after));
  108. DCHECK(IsValidSuffix(suffix));
  109. const std::string& mid = FindBetweenWithSuffix(
  110. Uncompress(before.compressed_), Uncompress(after.compressed_), suffix);
  111. return UniquePosition(mid + suffix, suffix);
  112. }
  113. UniquePosition::UniquePosition() = default;
  114. bool UniquePosition::LessThan(const UniquePosition& other) const {
  115. DCHECK(this->IsValid());
  116. DCHECK(other.IsValid());
  117. return compressed_ < other.compressed_;
  118. }
  119. bool UniquePosition::Equals(const UniquePosition& other) const {
  120. if (!this->IsValid() && !other.IsValid())
  121. return true;
  122. return compressed_ == other.compressed_;
  123. }
  124. sync_pb::UniquePosition UniquePosition::ToProto() const {
  125. sync_pb::UniquePosition proto;
  126. // This is the current preferred foramt.
  127. proto.set_custom_compressed_v1(compressed_);
  128. return proto;
  129. // Older clients used to write other formats. We don't bother doing that
  130. // anymore because that form of backwards compatibility is expensive. We no
  131. // longer want to pay that price just too support clients that have been
  132. // obsolete for a long time. See the proto definition for details.
  133. }
  134. void UniquePosition::SerializeToString(std::string* blob) const {
  135. DCHECK(blob);
  136. ToProto().SerializeToString(blob);
  137. }
  138. bool UniquePosition::IsValid() const {
  139. return !compressed_.empty();
  140. }
  141. std::string UniquePosition::ToDebugString() const {
  142. const std::string bytes = Uncompress(compressed_);
  143. if (bytes.empty())
  144. return std::string("INVALID[]");
  145. std::string debug_string = base::HexEncode(bytes.data(), bytes.length());
  146. if (!IsValid()) {
  147. debug_string = "INVALID[" + debug_string + "]";
  148. }
  149. std::string compressed_string =
  150. base::HexEncode(compressed_.data(), compressed_.length());
  151. debug_string.append(", compressed: " + compressed_string);
  152. return debug_string;
  153. }
  154. std::string UniquePosition::GetSuffixForTest() const {
  155. const std::string bytes = Uncompress(compressed_);
  156. const size_t prefix_len = bytes.length() - kSuffixLength;
  157. return bytes.substr(prefix_len, std::string::npos);
  158. }
  159. std::string UniquePosition::FindSmallerWithSuffix(const std::string& reference,
  160. const std::string& suffix) {
  161. size_t ref_zeroes = reference.find_first_not_of('\0');
  162. size_t suffix_zeroes = suffix.find_first_not_of('\0');
  163. // Neither of our inputs are allowed to have trailing zeroes, so the following
  164. // must be true.
  165. DCHECK_NE(ref_zeroes, std::string::npos);
  166. DCHECK_NE(suffix_zeroes, std::string::npos);
  167. if (suffix_zeroes > ref_zeroes) {
  168. // Implies suffix < ref.
  169. return std::string();
  170. }
  171. if (suffix.substr(suffix_zeroes) < reference.substr(ref_zeroes)) {
  172. // Prepend zeroes so the result has as many zero digits as |reference|.
  173. return std::string(ref_zeroes - suffix_zeroes, '\0');
  174. } else if (suffix_zeroes > 1) {
  175. // Prepend zeroes so the result has one more zero digit than |reference|.
  176. // We could also take the "else" branch below, but taking this branch will
  177. // give us a smaller result.
  178. return std::string(ref_zeroes - suffix_zeroes + 1, '\0');
  179. } else {
  180. // Prepend zeroes to match those in the |reference|, then something smaller
  181. // than the first non-zero digit in |reference|.
  182. char lt_digit = static_cast<uint8_t>(reference[ref_zeroes]) / 2;
  183. return std::string(ref_zeroes, '\0') + lt_digit;
  184. }
  185. }
  186. // static
  187. std::string UniquePosition::FindGreaterWithSuffix(const std::string& reference,
  188. const std::string& suffix) {
  189. size_t ref_FFs =
  190. reference.find_first_not_of(std::numeric_limits<uint8_t>::max());
  191. size_t suffix_FFs =
  192. suffix.find_first_not_of(std::numeric_limits<uint8_t>::max());
  193. if (ref_FFs == std::string::npos) {
  194. ref_FFs = reference.length();
  195. }
  196. if (suffix_FFs == std::string::npos) {
  197. suffix_FFs = suffix.length();
  198. }
  199. if (suffix_FFs > ref_FFs) {
  200. // Implies suffix > reference.
  201. return std::string();
  202. }
  203. if (suffix.substr(suffix_FFs) > reference.substr(ref_FFs)) {
  204. // Prepend FF digits to match those in |reference|.
  205. return std::string(ref_FFs - suffix_FFs,
  206. std::numeric_limits<uint8_t>::max());
  207. } else if (suffix_FFs > 1) {
  208. // Prepend enough leading FF digits so result has one more of them than
  209. // |reference| does. We could also take the "else" branch below, but this
  210. // gives us a smaller result.
  211. return std::string(ref_FFs - suffix_FFs + 1,
  212. std::numeric_limits<uint8_t>::max());
  213. } else {
  214. // Prepend FF digits to match those in |reference|, then something larger
  215. // than the first non-FF digit in |reference|.
  216. char gt_digit = static_cast<uint8_t>(reference[ref_FFs]) +
  217. (std::numeric_limits<uint8_t>::max() -
  218. static_cast<uint8_t>(reference[ref_FFs]) + 1) /
  219. 2;
  220. return std::string(ref_FFs, std::numeric_limits<uint8_t>::max()) + gt_digit;
  221. }
  222. }
  223. // static
  224. std::string UniquePosition::FindBetweenWithSuffix(const std::string& before,
  225. const std::string& after,
  226. const std::string& suffix) {
  227. DCHECK(IsValidSuffix(suffix));
  228. DCHECK_NE(before, after);
  229. DCHECK_LT(before, after);
  230. std::string mid;
  231. // Sometimes our suffix puts us where we want to be.
  232. if (before < suffix && suffix < after) {
  233. return std::string();
  234. }
  235. size_t i = 0;
  236. for (; i < std::min(before.length(), after.length()); ++i) {
  237. uint8_t a_digit = before[i];
  238. uint8_t b_digit = after[i];
  239. if (b_digit - a_digit >= 2) {
  240. mid.push_back(a_digit + (b_digit - a_digit) / 2);
  241. return mid;
  242. } else if (a_digit == b_digit) {
  243. mid.push_back(a_digit);
  244. // Both strings are equal so far. Will appending the suffix at this point
  245. // give us the comparison we're looking for?
  246. if (before.substr(i + 1) < suffix && suffix < after.substr(i + 1)) {
  247. return mid;
  248. }
  249. } else {
  250. DCHECK_EQ(b_digit - a_digit, 1); // Implied by above if branches.
  251. // The two options are off by one digit. The choice of whether to round
  252. // up or down here will have consequences on what we do with the remaining
  253. // digits. Exploring both options is an optimization and is not required
  254. // for the correctness of this algorithm.
  255. // Option A: Round down the current digit. This makes our |mid| <
  256. // |after|, no matter what we append afterwards. We then focus on
  257. // appending digits until |mid| > |before|.
  258. std::string mid_a = mid;
  259. mid_a.push_back(a_digit);
  260. mid_a.append(FindGreaterWithSuffix(before.substr(i + 1), suffix));
  261. // Option B: Round up the current digit. This makes our |mid| > |before|,
  262. // no matter what we append afterwards. We then focus on appending digits
  263. // until |mid| < |after|. Note that this option may not be viable if the
  264. // current digit is the last one in |after|, so we skip the option in that
  265. // case.
  266. if (after.length() > i + 1) {
  267. std::string mid_b = mid;
  268. mid_b.push_back(b_digit);
  269. mid_b.append(FindSmallerWithSuffix(after.substr(i + 1), suffix));
  270. // Does this give us a shorter position value? If so, use it.
  271. if (mid_b.length() < mid_a.length()) {
  272. return mid_b;
  273. }
  274. }
  275. return mid_a;
  276. }
  277. }
  278. // If we haven't found a midpoint yet, the following must be true:
  279. DCHECK_EQ(before.substr(0, i), after.substr(0, i));
  280. DCHECK_EQ(before, mid);
  281. DCHECK_LT(before.length(), after.length());
  282. // We know that we'll need to append at least one more byte to |mid| in the
  283. // process of making it < |after|. Appending any digit, regardless of the
  284. // value, will make |before| < |mid|. Therefore, the following will get us a
  285. // valid position.
  286. mid.append(FindSmallerWithSuffix(after.substr(i), suffix));
  287. return mid;
  288. }
  289. UniquePosition::UniquePosition(const std::string& compressed)
  290. : compressed_(IsValidBytes(Uncompress(compressed)) ? compressed
  291. : std::string()) {}
  292. UniquePosition::UniquePosition(const std::string& uncompressed,
  293. const std::string& suffix)
  294. : UniquePosition(Compress(uncompressed)) {
  295. DCHECK(uncompressed.rfind(suffix) + kSuffixLength == uncompressed.length());
  296. DCHECK(IsValidSuffix(suffix));
  297. DCHECK(IsValid());
  298. }
  299. // On custom compression:
  300. //
  301. // Let C(x) be the compression function and U(x) be the uncompression function.
  302. //
  303. // This compression scheme has a few special properties. For one, it is
  304. // order-preserving. For any two valid position strings x and y:
  305. // x < y <=> C(x) < C(y)
  306. // This allows us keep the position strings compressed as we sort them.
  307. //
  308. // The compressed format and the decode algorithm:
  309. //
  310. // The compressed string is a series of blocks, almost all of which are 8 bytes
  311. // in length. The only exception is the last block in the compressed string,
  312. // which may be a remainder block, which has length no greater than 7. The
  313. // full-length blocks are either repeated character blocks or plain data blocks.
  314. // All blocks are entirely self-contained. Their decoded values are independent
  315. // from that of their neighbours.
  316. //
  317. // A repeated character block is encoded into eight bytes and represents between
  318. // 4 and 2^31 repeated instances of a given character in the unencoded stream.
  319. // The encoding consists of a single character repeated four times, followed by
  320. // an encoded count. The encoded count is stored as a big-endian 32 bit
  321. // integer. There are 2^31 possible count values, and two encodings for each.
  322. // The high encoding is 'enc = kuint32max - count'; the low encoding is 'enc =
  323. // count'. At compression time, the algorithm will choose between the two
  324. // encodings based on which of the two will maintain the appropriate sort
  325. // ordering (by a process which will be described below). The decompression
  326. // algorithm need not concern itself with which encoding was used; it needs only
  327. // to decode it. The decoded value of this block is "count" instances of the
  328. // character that was repeated four times in the first half of this block.
  329. //
  330. // A plain data block is encoded into eight bytes and represents exactly eight
  331. // bytes of data in the unencoded stream. The plain data block must not begin
  332. // with the same character repeated four times. It is allowed to contain such a
  333. // four-character sequence, just not at the start of the block. The decoded
  334. // value of a plain data block is identical to its encoded value.
  335. //
  336. // A remainder block has length of at most seven. It is a shorter version of
  337. // the plain data block. It occurs only at the end of the encoded stream and
  338. // represents exactly as many bytes of unencoded data as its own length. Like a
  339. // plain data block, the remainder block never begins with the same character
  340. // repeated four times. The decoded value of this block is identical to its
  341. // encoded value.
  342. //
  343. // The encode algorithm:
  344. //
  345. // From the above description, it can be seen that there may be more than one
  346. // way to encode a given input string. The encoder must be careful to choose
  347. // the encoding that guarantees sort ordering.
  348. //
  349. // The rules for the encoder are as follows:
  350. // 1. Iterate through the input string and produce output blocks one at a time.
  351. // 2. Where possible (ie. where the next four bytes of input consist of the
  352. // same character repeated four times), produce a repeated data block of
  353. // maximum possible length.
  354. // 3. If there is at least 8 bytes of data remaining and it is not possible
  355. // to produce a repeated character block, produce a plain data block.
  356. // 4. If there are less than 8 bytes of data remaining and it is not possible
  357. // to produce a repeated character block, produce a remainder block.
  358. // 5. When producing a repeated character block, the count encoding must be
  359. // chosen in such a way that the sort ordering is maintained. The choice is
  360. // best illustrated by way of example:
  361. //
  362. // When comparing two strings, the first of which begins with of 8
  363. // instances of the letter 'B' and the second with 10 instances of the
  364. // letter 'B', which of the two should compare lower? The result depends
  365. // on the 9th character of the first string, since it will be compared
  366. // against the 9th 'B' in the second string. If that character is an 'A',
  367. // then the first string will compare lower. If it is a 'C', then the
  368. // first string will compare higher.
  369. //
  370. // The key insight is that the comparison value of a repeated character block
  371. // depends on the value of the character that follows it. If the character
  372. // follows the repeated character has a value greater than the repeated
  373. // character itself, then a shorter run length should translate to a higher
  374. // comparison value. Therefore, we encode its count using the low encoding.
  375. // Similarly, if the following character is lower, we use the high encoding.
  376. namespace {
  377. // Appends an encoded run length to |output_str|.
  378. static void WriteEncodedRunLength(uint32_t length,
  379. bool high_encoding,
  380. std::string* output_str) {
  381. CHECK_GE(length, 4U);
  382. CHECK_LT(length, 0x80000000);
  383. // Step 1: Invert the count, if necessary, to account for the following digit.
  384. uint32_t encoded_length;
  385. if (high_encoding) {
  386. encoded_length = 0xffffffff - length;
  387. } else {
  388. encoded_length = length;
  389. }
  390. // Step 2: Write it as big-endian so it compares correctly with memcmp(3).
  391. output_str->append(1, 0xff & (encoded_length >> 24U));
  392. output_str->append(1, 0xff & (encoded_length >> 16U));
  393. output_str->append(1, 0xff & (encoded_length >> 8U));
  394. output_str->append(1, 0xff & (encoded_length >> 0U));
  395. }
  396. // Reads an encoded run length for |str| at position |i|.
  397. static uint32_t ReadEncodedRunLength(const std::string& str, size_t i) {
  398. DCHECK_LE(i + 4, str.length());
  399. // Step 1: Extract the big-endian count.
  400. uint32_t encoded_length = (static_cast<uint8_t>(str[i + 3]) << 0) |
  401. (static_cast<uint8_t>(str[i + 2]) << 8) |
  402. (static_cast<uint8_t>(str[i + 1]) << 16) |
  403. (static_cast<uint8_t>(str[i + 0]) << 24);
  404. // Step 2: If this was an inverted count, un-invert it.
  405. uint32_t length;
  406. if (encoded_length & 0x80000000) {
  407. length = 0xffffffff - encoded_length;
  408. } else {
  409. length = encoded_length;
  410. }
  411. return length;
  412. }
  413. // A series of four identical chars at the beginning of a block indicates
  414. // the beginning of a repeated character block.
  415. static bool IsRepeatedCharPrefix(const std::string& chars, size_t start_index) {
  416. return chars[start_index] == chars[start_index + 1] &&
  417. chars[start_index] == chars[start_index + 2] &&
  418. chars[start_index] == chars[start_index + 3];
  419. }
  420. } // namespace
  421. // static
  422. // Wraps the CompressImpl function with a bunch of DCHECKs.
  423. std::string UniquePosition::Compress(const std::string& str) {
  424. DCHECK(IsValidBytes(str));
  425. std::string compressed = CompressImpl(str);
  426. DCHECK(IsValidCompressed(compressed));
  427. DCHECK_EQ(str, Uncompress(compressed));
  428. return compressed;
  429. }
  430. // static
  431. // Performs the order preserving run length compression of a given input string.
  432. std::string UniquePosition::CompressImpl(const std::string& str) {
  433. std::string output;
  434. // The compressed length will usually be at least as long as the suffix (28),
  435. // since the suffix bytes are mostly random. Most are a few bytes longer; a
  436. // small few are tens of bytes longer. Some early tests indicated that
  437. // roughly 99% had length 40 or smaller. We guess that pre-sizing for 48 is a
  438. // good trade-off, but that has not been confirmed through profiling.
  439. output.reserve(48);
  440. // Each loop iteration will consume 8, or N bytes, where N >= 4 and is the
  441. // length of a string of identical digits starting at i.
  442. for (size_t i = 0; i < str.length();) {
  443. if (i + 4 <= str.length() && IsRepeatedCharPrefix(str, i)) {
  444. // Four identical bytes in a row at this position means that we must start
  445. // a repeated character block. Begin by outputting those four bytes.
  446. output.append(str, i, 4);
  447. // Determine the size of the run.
  448. const char rep_digit = str[i];
  449. const size_t runs_until = str.find_first_not_of(rep_digit, i + 4);
  450. // Handle the 'runs until end' special case specially.
  451. size_t run_length;
  452. bool encode_high; // True if the next byte is greater than |rep_digit|.
  453. if (runs_until == std::string::npos) {
  454. run_length = str.length() - i;
  455. encode_high = false;
  456. } else {
  457. run_length = runs_until - i;
  458. encode_high = static_cast<uint8_t>(str[runs_until]) >
  459. static_cast<uint8_t>(rep_digit);
  460. }
  461. DCHECK_LT(run_length,
  462. static_cast<size_t>(std::numeric_limits<int32_t>::max()))
  463. << "This implementation can't encode run-lengths greater than 2^31.";
  464. WriteEncodedRunLength(run_length, encode_high, &output);
  465. i += run_length; // Jump forward by the size of the run length.
  466. } else {
  467. // Output up to eight bytes without any encoding.
  468. const size_t len = std::min(static_cast<size_t>(8), str.length() - i);
  469. output.append(str, i, len);
  470. i += len; // Jump forward by the amount of input consumed (usually 8).
  471. }
  472. }
  473. return output;
  474. }
  475. // static
  476. // Uncompresses strings that were compresed with UniquePosition::Compress.
  477. std::string UniquePosition::Uncompress(const std::string& str) {
  478. std::string output;
  479. size_t i = 0;
  480. // Iterate through the compressed string one block at a time.
  481. for (i = 0; i + 8 <= str.length(); i += 8) {
  482. if (IsRepeatedCharPrefix(str, i)) {
  483. // Found a repeated character block. Expand it.
  484. const char rep_digit = str[i];
  485. uint32_t length = ReadEncodedRunLength(str, i + 4);
  486. output.append(length, rep_digit);
  487. } else {
  488. // Found a regular block. Copy it.
  489. output.append(str, i, 8);
  490. }
  491. }
  492. // Copy the remaining bytes that were too small to form a block.
  493. output.append(str, i, std::string::npos);
  494. return output;
  495. }
  496. bool UniquePosition::IsValidCompressed(const std::string& str) {
  497. for (size_t i = 0; i + 8 <= str.length(); i += 8) {
  498. if (IsRepeatedCharPrefix(str, i)) {
  499. uint32_t count = ReadEncodedRunLength(str, i + 4);
  500. if (count < 4) {
  501. // A repeated character block should at least represent the four
  502. // characters that started it.
  503. return false;
  504. }
  505. if (str[i] == str[i + 4]) {
  506. // Does the next digit after a count match the repeated character? Then
  507. // this is not the highest possible count.
  508. return false;
  509. }
  510. }
  511. }
  512. // We don't bother looking for the existence or checking the validity of
  513. // any partial blocks. There's no way they could be invalid anyway.
  514. return true;
  515. }
  516. size_t UniquePosition::EstimateMemoryUsage() const {
  517. using base::trace_event::EstimateMemoryUsage;
  518. return EstimateMemoryUsage(compressed_);
  519. }
  520. } // namespace syncer