encoded_view.h 5.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185
  1. // Copyright 2017 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. #ifndef COMPONENTS_ZUCCHINI_ENCODED_VIEW_H_
  5. #define COMPONENTS_ZUCCHINI_ENCODED_VIEW_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <iterator>
  9. #include <vector>
  10. #include "components/zucchini/image_index.h"
  11. #include "components/zucchini/image_utils.h"
  12. namespace zucchini {
  13. // Zucchini-gen performs semantics-aware matching:
  14. // - Same-typed reference target in "old" and "new" can be associated.
  15. // Associated targets are assigned an identifier called "label" (and for
  16. // unassociated targets, label = 0).
  17. // - EncodedView maps each offset in "old" and "new" images to a "projected
  18. // value", which can be:
  19. // - Raw byte value (0-255) for non-references.
  20. // - Reference "projected value" (> 256) that depends on target {type, label}
  21. // at each reference's location (byte 0).
  22. // - Reference padding value (256) at the body of each reference (bytes 1+).
  23. // - The projected values for "old" and "new" are used to build the equivalence
  24. // map.
  25. constexpr size_t kReferencePaddingProjection = 256;
  26. constexpr size_t kBaseReferenceProjection = 257;
  27. // A Range (providing begin and end iterators) that adapts ImageIndex to make
  28. // image data appear as an Encoded Image, that is encoded data under a higher
  29. // level of abstraction than raw bytes. In particular:
  30. // - First byte of each reference become a projection of its type and label.
  31. // - Subsequent bytes of each reference becomes |kReferencePaddingProjection|.
  32. // - Non-reference raw bytes remain as raw bytes.
  33. class EncodedView {
  34. public:
  35. // RandomAccessIterator whose values are the results of Projection().
  36. class Iterator {
  37. public:
  38. using iterator_category = std::random_access_iterator_tag;
  39. using value_type = size_t;
  40. using difference_type = ptrdiff_t;
  41. using reference = size_t;
  42. using pointer = size_t*;
  43. Iterator(const EncodedView* encoded_view, difference_type pos)
  44. : encoded_view_(encoded_view), pos_(pos) {}
  45. Iterator(const Iterator&) = default;
  46. Iterator& operator=(const Iterator&) = default;
  47. value_type operator*() const {
  48. return encoded_view_->Projection(static_cast<offset_t>(pos_));
  49. }
  50. value_type operator[](difference_type n) const {
  51. return encoded_view_->Projection(static_cast<offset_t>(pos_ + n));
  52. }
  53. Iterator& operator++() {
  54. ++pos_;
  55. return *this;
  56. }
  57. Iterator operator++(int) {
  58. Iterator tmp = *this;
  59. ++pos_;
  60. return tmp;
  61. }
  62. Iterator& operator--() {
  63. --pos_;
  64. return *this;
  65. }
  66. Iterator operator--(int) {
  67. Iterator tmp = *this;
  68. --pos_;
  69. return tmp;
  70. }
  71. Iterator& operator+=(difference_type n) {
  72. pos_ += n;
  73. return *this;
  74. }
  75. Iterator& operator-=(difference_type n) {
  76. pos_ -= n;
  77. return *this;
  78. }
  79. friend bool operator==(Iterator a, Iterator b) { return a.pos_ == b.pos_; }
  80. friend bool operator!=(Iterator a, Iterator b) { return !(a == b); }
  81. friend bool operator<(Iterator a, Iterator b) { return a.pos_ < b.pos_; }
  82. friend bool operator>(Iterator a, Iterator b) { return b < a; }
  83. friend bool operator<=(Iterator a, Iterator b) { return !(b < a); }
  84. friend bool operator>=(Iterator a, Iterator b) { return !(a < b); }
  85. friend difference_type operator-(Iterator a, Iterator b) {
  86. return a.pos_ - b.pos_;
  87. }
  88. friend Iterator operator+(Iterator it, difference_type n) {
  89. it += n;
  90. return it;
  91. }
  92. friend Iterator operator-(Iterator it, difference_type n) {
  93. it -= n;
  94. return it;
  95. }
  96. private:
  97. const EncodedView* encoded_view_;
  98. difference_type pos_;
  99. };
  100. using value_type = size_t;
  101. using size_type = offset_t;
  102. using difference_type = ptrdiff_t;
  103. using const_iterator = Iterator;
  104. // |image_index| is the annotated image being adapted, and is required to
  105. // remain valid for the lifetime of the object.
  106. explicit EncodedView(const ImageIndex& image_index);
  107. EncodedView(const EncodedView&) = delete;
  108. const EncodedView& operator=(const EncodedView&) = delete;
  109. ~EncodedView();
  110. // Projects |location| to a scalar value that describes the content at a
  111. // higher level of abstraction.
  112. value_type Projection(offset_t location) const;
  113. bool IsToken(offset_t location) const {
  114. return image_index_.IsToken(location);
  115. }
  116. // Returns the cardinality of the projection, i.e., the upper bound on
  117. // values returned by Projection().
  118. value_type Cardinality() const;
  119. // Associates |labels| to targets for a given |pool|, replacing previous
  120. // association. Values in |labels| must be smaller than |bound|.
  121. void SetLabels(PoolTag pool, std::vector<uint32_t>&& labels, size_t bound);
  122. const ImageIndex& image_index() const { return image_index_; }
  123. // Range functions.
  124. size_type size() const { return size_type(image_index_.size()); }
  125. const_iterator begin() const {
  126. return const_iterator{this, difference_type(0)};
  127. }
  128. const_iterator end() const {
  129. return const_iterator{this, difference_type(size())};
  130. }
  131. private:
  132. struct PoolInfo {
  133. PoolInfo();
  134. PoolInfo(PoolInfo&&);
  135. ~PoolInfo();
  136. // |labels| translates IndirectReference target_key to label.
  137. std::vector<uint32_t> labels;
  138. size_t bound = 0;
  139. };
  140. const ImageIndex& image_index_;
  141. std::vector<PoolInfo> pool_infos_;
  142. };
  143. } // namespace zucchini
  144. #endif // COMPONENTS_ZUCCHINI_ENCODED_VIEW_H_