OLD | NEW |
1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "pdf/chunk_stream.h" | 5 #include "pdf/chunk_stream.h" |
6 | 6 |
7 #include <stddef.h> | 7 #include <stddef.h> |
8 #include <string.h> | 8 #include <string.h> |
9 | 9 |
10 #define __STDC_LIMIT_MACROS | |
11 #ifdef _WIN32 | |
12 #include <limits.h> | |
13 #else | |
14 #include <stdint.h> | |
15 #endif | |
16 | |
17 #include <algorithm> | 10 #include <algorithm> |
| 11 #include <limits> |
18 | 12 |
19 namespace chrome_pdf { | 13 namespace chrome_pdf { |
20 | 14 |
21 ChunkStream::ChunkStream() : stream_size_(0) {} | 15 ChunkStream::ChunkStream() : stream_size_(0) {} |
22 | 16 |
23 ChunkStream::~ChunkStream() {} | 17 ChunkStream::~ChunkStream() {} |
24 | 18 |
25 void ChunkStream::Clear() { | 19 void ChunkStream::Clear() { |
26 chunks_.clear(); | 20 chunks_.clear(); |
27 data_.clear(); | 21 data_.clear(); |
28 stream_size_ = 0; | 22 stream_size_ = 0; |
29 } | 23 } |
30 | 24 |
31 void ChunkStream::Preallocate(size_t stream_size) { | 25 void ChunkStream::Preallocate(size_t stream_size) { |
32 data_.reserve(stream_size); | 26 data_.reserve(stream_size); |
33 stream_size_ = stream_size; | 27 stream_size_ = stream_size; |
34 } | 28 } |
35 | 29 |
36 size_t ChunkStream::GetSize() const { | 30 size_t ChunkStream::GetSize() const { |
37 return data_.size(); | 31 return data_.size(); |
38 } | 32 } |
39 | 33 |
40 bool ChunkStream::WriteData(size_t offset, void* buffer, size_t size) { | 34 bool ChunkStream::WriteData(size_t offset, void* buffer, size_t size) { |
41 if (SIZE_MAX - size < offset) | 35 if (std::numeric_limits<size_t>::max() - size < offset) |
42 return false; | 36 return false; |
43 | 37 |
44 if (data_.size() < offset + size) | 38 if (data_.size() < offset + size) |
45 data_.resize(offset + size); | 39 data_.resize(offset + size); |
46 | 40 |
47 memcpy(&data_[offset], buffer, size); | 41 memcpy(&data_[offset], buffer, size); |
48 | 42 |
49 if (chunks_.empty()) { | 43 if (chunks_.empty()) { |
50 chunks_[offset] = size; | 44 chunks_[offset] = size; |
51 return true; | 45 return true; |
52 } | 46 } |
53 | 47 |
54 std::map<size_t, size_t>::iterator start = chunks_.upper_bound(offset); | 48 auto start = GetStartChunk(offset); |
55 if (start != chunks_.begin()) | 49 auto end = chunks_.upper_bound(offset + size); |
56 --start; // start now points to the key equal or lower than offset. | |
57 if (start->first + start->second < offset) | |
58 ++start; // start element is entirely before current chunk, skip it. | |
59 | |
60 std::map<size_t, size_t>::iterator end = chunks_.upper_bound(offset + size); | |
61 if (start == end) { // No chunks to merge. | 50 if (start == end) { // No chunks to merge. |
62 chunks_[offset] = size; | 51 chunks_[offset] = size; |
63 return true; | 52 return true; |
64 } | 53 } |
65 | 54 |
66 --end; | 55 auto prev = end; |
| 56 --prev; |
| 57 size_t prev_size = prev->first + prev->second; |
67 | 58 |
68 size_t new_offset = std::min<size_t>(start->first, offset); | 59 size_t new_offset = std::min<size_t>(start->first, offset); |
69 size_t new_size = | 60 size_t new_size = std::max<size_t>(prev_size, offset + size) - new_offset; |
70 std::max<size_t>(end->first + end->second, offset + size) - new_offset; | |
71 | 61 |
72 chunks_.erase(start, ++end); | 62 chunks_.erase(start, end); |
73 | |
74 chunks_[new_offset] = new_size; | 63 chunks_[new_offset] = new_size; |
75 | |
76 return true; | 64 return true; |
77 } | 65 } |
78 | 66 |
79 bool ChunkStream::ReadData(size_t offset, size_t size, void* buffer) const { | 67 bool ChunkStream::ReadData(size_t offset, size_t size, void* buffer) const { |
80 if (!IsRangeAvailable(offset, size)) | 68 if (!IsRangeAvailable(offset, size)) |
81 return false; | 69 return false; |
82 | 70 |
83 memcpy(buffer, &data_[offset], size); | 71 memcpy(buffer, &data_[offset], size); |
84 return true; | 72 return true; |
85 } | 73 } |
86 | 74 |
87 bool ChunkStream::GetMissedRanges( | 75 bool ChunkStream::GetMissedRanges( |
88 size_t offset, | 76 size_t offset, |
89 size_t size, | 77 size_t size, |
90 std::vector<std::pair<size_t, size_t>>* ranges) const { | 78 std::vector<std::pair<size_t, size_t>>* ranges) const { |
91 if (IsRangeAvailable(offset, size)) | 79 if (IsRangeAvailable(offset, size)) |
92 return false; | 80 return false; |
93 | 81 |
94 ranges->clear(); | 82 ranges->clear(); |
95 if (chunks_.empty()) { | 83 if (chunks_.empty()) { |
96 ranges->push_back(std::pair<size_t, size_t>(offset, size)); | 84 ranges->push_back(std::pair<size_t, size_t>(offset, size)); |
97 return true; | 85 return true; |
98 } | 86 } |
99 | 87 |
100 std::map<size_t, size_t>::const_iterator start = chunks_.upper_bound(offset); | 88 auto start = GetStartChunk(offset); |
101 if (start != chunks_.begin()) | 89 auto end = chunks_.upper_bound(offset + size); |
102 --start; // start now points to the key equal or lower than offset. | |
103 if (start->first + start->second < offset) | |
104 ++start; // start element is entirely before current chunk, skip it. | |
105 | |
106 std::map<size_t, size_t>::const_iterator end = | |
107 chunks_.upper_bound(offset + size); | |
108 if (start == end) { // No data in the current range available. | 90 if (start == end) { // No data in the current range available. |
109 ranges->push_back(std::pair<size_t, size_t>(offset, size)); | 91 ranges->push_back(std::pair<size_t, size_t>(offset, size)); |
110 return true; | 92 return true; |
111 } | 93 } |
112 | 94 |
113 size_t cur_offset = offset; | 95 size_t cur_offset = offset; |
114 std::map<size_t, size_t>::const_iterator it; | 96 for (auto it = start; it != end; ++it) { |
115 for (it = start; it != end; ++it) { | |
116 if (cur_offset < it->first) { | 97 if (cur_offset < it->first) { |
117 size_t new_size = it->first - cur_offset; | 98 size_t new_size = it->first - cur_offset; |
118 ranges->push_back(std::pair<size_t, size_t>(cur_offset, new_size)); | 99 ranges->push_back(std::pair<size_t, size_t>(cur_offset, new_size)); |
119 cur_offset = it->first + it->second; | 100 cur_offset = it->first + it->second; |
120 } else if (cur_offset < it->first + it->second) { | 101 } else if (cur_offset < it->first + it->second) { |
121 cur_offset = it->first + it->second; | 102 cur_offset = it->first + it->second; |
122 } | 103 } |
123 } | 104 } |
124 | 105 |
125 // Add last chunk. | 106 // Add last chunk. |
126 if (cur_offset < offset + size) | 107 if (cur_offset < offset + size) { |
127 ranges->push_back( | 108 ranges->push_back( |
128 std::pair<size_t, size_t>(cur_offset, offset + size - cur_offset)); | 109 std::pair<size_t, size_t>(cur_offset, offset + size - cur_offset)); |
| 110 } |
129 | 111 |
130 return true; | 112 return true; |
131 } | 113 } |
132 | 114 |
133 bool ChunkStream::IsRangeAvailable(size_t offset, size_t size) const { | 115 bool ChunkStream::IsRangeAvailable(size_t offset, size_t size) const { |
134 if (chunks_.empty()) | 116 if (chunks_.empty()) |
135 return false; | 117 return false; |
136 | 118 |
137 if (SIZE_MAX - size < offset) | 119 if (std::numeric_limits<size_t>::max() - size < offset) |
138 return false; | 120 return false; |
139 | 121 |
140 std::map<size_t, size_t>::const_iterator it = chunks_.upper_bound(offset); | 122 auto it = chunks_.upper_bound(offset); |
141 if (it == chunks_.begin()) | 123 if (it == chunks_.begin()) |
142 return false; // No chunks includes offset byte. | 124 return false; // No chunks includes offset byte. |
143 | 125 |
144 --it; // Now it starts equal or before offset. | 126 --it; // Now it starts equal or before offset. |
145 return (it->first + it->second) >= (offset + size); | 127 return it->first + it->second >= offset + size; |
146 } | 128 } |
147 | 129 |
148 size_t ChunkStream::GetFirstMissingByte() const { | 130 size_t ChunkStream::GetFirstMissingByte() const { |
149 if (chunks_.empty()) | 131 if (chunks_.empty()) |
150 return 0; | 132 return 0; |
151 std::map<size_t, size_t>::const_iterator begin = chunks_.begin(); | 133 auto begin = chunks_.begin(); |
152 return begin->first > 0 ? 0 : begin->second; | 134 return begin->first > 0 ? 0 : begin->second; |
153 } | 135 } |
154 | 136 |
155 size_t ChunkStream::GetFirstMissingByteInInterval(size_t offset) const { | 137 size_t ChunkStream::GetFirstMissingByteInInterval(size_t offset) const { |
156 if (chunks_.empty()) | 138 if (chunks_.empty()) |
157 return 0; | 139 return 0; |
158 std::map<size_t, size_t>::const_iterator it = chunks_.upper_bound(offset); | 140 auto it = chunks_.upper_bound(offset); |
159 if (it == chunks_.begin()) | 141 if (it == chunks_.begin()) |
160 return 0; | 142 return 0; |
161 --it; | 143 --it; |
162 return it->first + it->second; | 144 return it->first + it->second; |
163 } | 145 } |
164 | 146 |
165 size_t ChunkStream::GetLastMissingByteInInterval(size_t offset) const { | 147 size_t ChunkStream::GetLastMissingByteInInterval(size_t offset) const { |
166 if (chunks_.empty()) | 148 if (chunks_.empty()) |
167 return stream_size_ - 1; | 149 return stream_size_ - 1; |
168 std::map<size_t, size_t>::const_iterator it = chunks_.upper_bound(offset); | 150 auto it = chunks_.upper_bound(offset); |
169 if (it == chunks_.end()) | 151 if (it == chunks_.end()) |
170 return stream_size_ - 1; | 152 return stream_size_ - 1; |
171 return it->first - 1; | 153 return it->first - 1; |
172 } | 154 } |
173 | 155 |
| 156 std::map<size_t, size_t>::const_iterator ChunkStream::GetStartChunk( |
| 157 size_t offset) const { |
| 158 auto start = chunks_.upper_bound(offset); |
| 159 if (start != chunks_.begin()) |
| 160 --start; // start now points to the key equal or lower than offset. |
| 161 if (start->first + start->second < offset) |
| 162 ++start; // start element is entirely before current chunk, skip it. |
| 163 return start; |
| 164 } |
| 165 |
174 } // namespace chrome_pdf | 166 } // namespace chrome_pdf |
OLD | NEW |