1 : // Copyright 2012 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 : #include "syzygy/block_graph/block_graph_serializer.h"
16 :
17 : #include "base/stringprintf.h"
18 :
19 : namespace block_graph {
20 :
21 : namespace {
22 :
23 : using core::InArchive;
24 : using core::OutArchive;
25 :
26 : // This needs to be incremented any time a any non-backwards compatible change
27 : // is made to the serialization format.
28 : // TODO(chrisha): Enforce this via a unittest. Check in a version of a
29 : // simple block-graph, and ensure it deserializes to the same in-memory
30 : // representation.
31 : static const uint32 kSerializedBlockGraphVersion = 1;
32 :
33 : // Potentially saves a string, depending on whether or not OMIT_STRINGS is
34 : // enabled.
35 : bool MaybeSaveString(const BlockGraphSerializer& bgs,
36 : const std::string& value,
37 E : OutArchive* out_archive) {
38 E : DCHECK(out_archive != NULL);
39 :
40 E : if (bgs.has_attributes(BlockGraphSerializer::OMIT_STRINGS))
41 E : return true;
42 :
43 E : if (!out_archive->Save(value)) {
44 i : LOG(ERROR) << "Unable to save string \"" << value << "\".";
45 i : return false;
46 : }
47 :
48 E : return true;
49 E : }
50 :
51 : // Potentially loads a string, depending on whether or not OMIT_STRINGS is
52 : // enabled.
53 : bool MaybeLoadString(const BlockGraphSerializer& bgs,
54 : std::string* value,
55 E : InArchive* in_archive) {
56 E : DCHECK(value != NULL);
57 E : DCHECK(in_archive != NULL);
58 :
59 E : if (bgs.has_attributes(BlockGraphSerializer::OMIT_STRINGS))
60 E : return true;
61 :
62 E : if (!in_archive->Load(value)) {
63 i : LOG(ERROR) << "Unable to load string.";
64 i : return false;
65 : }
66 :
67 E : return true;
68 E : }
69 :
70 E : bool ValidAttributes(uint32 attributes, uint32 attributes_max) {
71 E : return (attributes & ~(attributes_max - 1)) == 0;
72 E : }
73 :
74 : } // namespace
75 :
76 : bool BlockGraphSerializer::Save(const BlockGraph& block_graph,
77 E : core::OutArchive* out_archive) const {
78 E : CHECK(out_archive != NULL);
79 :
80 : // Save the serialization attributes so we can read this block-graph without
81 : // having to be told how it was saved.
82 : if (!out_archive->Save(kSerializedBlockGraphVersion) ||
83 : !out_archive->Save(static_cast<uint32>(data_mode_)) ||
84 E : !out_archive->Save(attributes_)) {
85 i : LOG(ERROR) << "Unable to save serialized block-graph properties.";
86 i : return false;
87 : }
88 :
89 : // This function takes care of outputting a meaningful log message on
90 : // failure.
91 E : if (!SaveBlockGraphProperties(block_graph, out_archive))
92 i : return false;
93 :
94 : // Save the blocks, except for their references. We do that in a second pass
95 : // so that when loading the referenced blocks will exist.
96 E : if (!SaveBlocks(block_graph, out_archive)) {
97 i : LOG(ERROR) << "Unable to save blocks.";
98 i : return false;
99 : }
100 :
101 : // Save all of the references. The referrers are implicitly saved by this.
102 E : if (!SaveBlockGraphReferences(block_graph, out_archive)) {
103 i : LOG(ERROR) << "Unable to save block graph references.";
104 i : return false;
105 : }
106 :
107 E : return true;
108 E : }
109 :
110 : bool BlockGraphSerializer::Load(BlockGraph* block_graph,
111 E : core::InArchive* in_archive) {
112 E : CHECK(block_graph != NULL);
113 E : CHECK(in_archive != NULL);
114 :
115 E : uint32 version = 0;
116 E : if (!in_archive->Load(&version)) {
117 i : LOG(ERROR) << "Unable to load serialized block graph version.";
118 i : return false;
119 : }
120 :
121 : // Here's is where we could dispatch to different load functions for
122 : // backwards compatibility with previous versions. For now, we simply bail.
123 E : if (version != kSerializedBlockGraphVersion) {
124 E : LOG(ERROR) << "Unable to load block graph with version " << version
125 : << " (expected " << kSerializedBlockGraphVersion << ").";
126 E : return false;
127 : }
128 :
129 : // Read the serialization attributes and mode information so that we know how
130 : // to load the block-graph.
131 E : uint32 data_mode = 0;
132 E : if (!in_archive->Load(&data_mode) || !in_archive->Load(&attributes_)) {
133 i : LOG(ERROR) << "Unable to load serialized block-graph properties.";
134 i : return false;
135 : }
136 E : data_mode_ = static_cast<DataMode>(data_mode);
137 :
138 : // Ensure that the data mode and the attributes are valid.
139 : if (data_mode_ >= DATA_MODE_MAX ||
140 E : !ValidAttributes(attributes_, ATTRIBUTES_MAX)) {
141 i : LOG(ERROR) << "Invalid data mode and/or attributes.";
142 i : return false;
143 : }
144 :
145 : // This function takes care of outputting a meaningful log message on
146 : // failure.
147 E : if (!LoadBlockGraphProperties(block_graph, in_archive))
148 i : return false;
149 :
150 : // Load the blocks, except for their references.
151 E : if (!LoadBlocks(block_graph, in_archive)) {
152 i : LOG(ERROR) << "Unable to load blocks.";
153 i : return false;
154 : }
155 :
156 : // Now load the references and wire them up.
157 E : if (!LoadBlockGraphReferences(block_graph, in_archive)) {
158 i : LOG(ERROR) << "Unable to load block graph references.";
159 i : return false;
160 : }
161 :
162 E : return true;
163 E : }
164 :
165 : bool BlockGraphSerializer::SaveBlockGraphProperties(
166 : const BlockGraph& block_graph,
167 E : OutArchive* out_archive) const {
168 E : DCHECK(out_archive != NULL);
169 :
170 : if (!out_archive->Save(block_graph.next_section_id_) ||
171 : !out_archive->Save(block_graph.sections_) ||
172 E : !out_archive->Save(block_graph.next_block_id_)) {
173 i : LOG(ERROR) << "Unable to save block graph properties.";
174 i : return false;
175 : }
176 :
177 E : return true;
178 E : }
179 :
180 : bool BlockGraphSerializer::LoadBlockGraphProperties(
181 E : BlockGraph* block_graph, InArchive* in_archive) const {
182 E : DCHECK(block_graph != NULL);
183 E : DCHECK(in_archive != NULL);
184 :
185 : // The block graph properties should be empty.
186 E : DCHECK_EQ(0u, block_graph->next_section_id_);
187 E : DCHECK_EQ(0u, block_graph->sections_.size());
188 E : DCHECK_EQ(0u, block_graph->next_block_id_);
189 :
190 : if (!in_archive->Load(&block_graph->next_section_id_) ||
191 : !in_archive->Load(&block_graph->sections_) ||
192 E : !in_archive->Load(&block_graph->next_block_id_)) {
193 i : LOG(ERROR) << "Unable to load block graph properties.";
194 i : return false;
195 : }
196 :
197 E : return true;
198 E : }
199 :
200 : bool BlockGraphSerializer::SaveBlocks(const BlockGraph& block_graph,
201 E : OutArchive* out_archive) const {
202 E : DCHECK(out_archive != NULL);
203 :
204 E : if (!out_archive->Save(block_graph.blocks().size())) {
205 i : LOG(ERROR) << "Unable to save block count.";
206 i : return false;
207 : }
208 :
209 : // Output the basic block properties first.
210 E : BlockGraph::BlockMap::const_iterator it = block_graph.blocks_.begin();
211 E : for (; it != block_graph.blocks_.end(); ++it) {
212 E : BlockGraph::BlockId block_id = it->first;
213 E : const BlockGraph::Block& block = it->second;
214 : if (!out_archive->Save(block_id) ||
215 : !SaveBlockProperties(block, out_archive) ||
216 : !SaveBlockLabels(block, out_archive) ||
217 E : !SaveBlockData(block, out_archive)) {
218 i : LOG(ERROR) << "Unable to save block with id " << block_id << ".";
219 i : return false;
220 : }
221 E : }
222 :
223 E : return true;
224 E : }
225 :
226 : bool BlockGraphSerializer::LoadBlocks(BlockGraph* block_graph,
227 E : InArchive* in_archive) const {
228 E : DCHECK(block_graph != NULL);
229 E : DCHECK(in_archive != NULL);
230 :
231 E : DCHECK_EQ(0u, block_graph->blocks_.size());
232 :
233 E : size_t count = 0;
234 E : if (!in_archive->Load(&count)) {
235 i : LOG(ERROR) << "Unable to load block count.";
236 i : return false;
237 : }
238 :
239 E : for (size_t i = 0; i < count; ++i) {
240 E : BlockGraph::BlockId id = 0;
241 E : if (!in_archive->Load(&id)) {
242 i : LOG(ERROR) << "Unable to load id for block " << i << " of " << count
243 : << ".";
244 i : return false;
245 : }
246 :
247 : std::pair<BlockGraph::BlockMap::iterator, bool> result =
248 : block_graph->blocks_.insert(
249 E : std::make_pair(id, BlockGraph::Block(block_graph)));
250 E : if (!result.second) {
251 i : LOG(ERROR) << "Unable to insert block with id " << id << ".";
252 i : return false;
253 : }
254 E : BlockGraph::Block* block = &result.first->second;
255 E : block->id_ = id;
256 :
257 : if (!LoadBlockProperties(block, in_archive) ||
258 : !LoadBlockLabels(block, in_archive) ||
259 E : !LoadBlockData(block, in_archive)) {
260 i : LOG(ERROR) << "Unable to load block " << i << " of " << count
261 : << " with id " << id << ".";
262 i : return false;
263 : }
264 E : }
265 E : DCHECK_EQ(count, block_graph->blocks_.size());
266 :
267 E : return true;
268 E : }
269 :
270 : bool BlockGraphSerializer::SaveBlockGraphReferences(
271 E : const BlockGraph& block_graph, OutArchive* out_archive) const {
272 E : DCHECK(out_archive != NULL);
273 :
274 E : BlockGraph::BlockMap::const_iterator it = block_graph.blocks().begin();
275 E : for (; it != block_graph.blocks().end(); ++it) {
276 E : if (!SaveBlockReferences(it->second, out_archive)) {
277 i : LOG(ERROR) << "Unable to save references for block with id "
278 : << it->second.id() << ".";
279 i : return false;
280 : }
281 E : }
282 :
283 E : return true;
284 E : }
285 :
286 : bool BlockGraphSerializer::LoadBlockGraphReferences(
287 E : BlockGraph* block_graph, InArchive* in_archive) const {
288 E : DCHECK(block_graph != NULL);
289 E : DCHECK(in_archive != NULL);
290 :
291 E : BlockGraph::BlockMap::iterator it = block_graph->blocks_mutable().begin();
292 E : for (; it != block_graph->blocks_mutable().end(); ++it) {
293 E : if (!LoadBlockReferences(block_graph, &it->second, in_archive)) {
294 i : LOG(ERROR) << "Unable to load references for block with id "
295 : << it->second.id() << ".";
296 i : return false;
297 : }
298 E : }
299 :
300 E : return true;
301 E : }
302 :
303 : bool BlockGraphSerializer::SaveBlockProperties(const BlockGraph::Block& block,
304 E : OutArchive* out_archive) const {
305 E : DCHECK(out_archive != NULL);
306 :
307 : COMPILE_ASSERT(BlockGraph::BLOCK_ATTRIBUTES_MAX <= (1 << 16),
308 : block_attributes_need_more_than_16_bits);
309 :
310 E : uint8 type = static_cast<uint8>(block.type());
311 E : uint16 attributes = static_cast<uint16>(block.attributes());
312 :
313 : // We use a signed integer for saving the section ID, as -1 is used to
314 : // indicate 'no section'.
315 : if (!out_archive->Save(type) ||
316 : !SaveUint32(block.size(), out_archive) ||
317 : !SaveUint32(block.alignment(), out_archive) ||
318 : !out_archive->Save(block.source_ranges()) ||
319 : !out_archive->Save(block.addr()) ||
320 : !SaveInt32(static_cast<uint32>(block.section()), out_archive) ||
321 : !out_archive->Save(attributes) ||
322 E : !MaybeSaveString(*this, block.name(), out_archive)) {
323 i : LOG(ERROR) << "Unable to save properties for block with id "
324 : << block.id() << ".";
325 i : return false;
326 : }
327 :
328 E : return true;
329 E : }
330 :
331 : bool BlockGraphSerializer::LoadBlockProperties(BlockGraph::Block* block,
332 E : InArchive* in_archive) const {
333 E : DCHECK(block != NULL);
334 E : DCHECK(in_archive != NULL);
335 :
336 : // Make sure the block is freshly initialized.
337 E : DCHECK_EQ(BlockGraph::CODE_BLOCK, block->type_);
338 E : DCHECK_EQ(0u, block->size_);
339 E : DCHECK_EQ(1u, block->alignment_);
340 E : DCHECK_EQ(0u, block->source_ranges_.size());
341 E : DCHECK_EQ(kInvalidAddress, block->addr_);
342 E : DCHECK_EQ(BlockGraph::kInvalidSectionId, block->section_);
343 E : DCHECK_EQ(0u, block->attributes_);
344 :
345 E : uint8 type = 0;
346 E : uint32 size = 0;
347 E : uint32 alignment = 0;
348 E : uint32 section = 0;
349 E : uint16 attributes = 0;
350 : if (!in_archive->Load(&type) ||
351 : !LoadUint32(&size, in_archive) ||
352 : !LoadUint32(&alignment, in_archive) ||
353 : !in_archive->Load(&block->source_ranges_) ||
354 : !in_archive->Load(&block->addr_) ||
355 : !LoadInt32(reinterpret_cast<int32*>(§ion), in_archive) ||
356 : !in_archive->Load(&attributes) ||
357 E : !MaybeLoadString(*this, &block->name_, in_archive)) {
358 i : LOG(ERROR) << "Unable to load properties for block with id "
359 : << block->id() << ".";
360 i : return false;
361 : }
362 :
363 : if (type > BlockGraph::BLOCK_TYPE_MAX ||
364 E : !ValidAttributes(attributes, BlockGraph::BLOCK_ATTRIBUTES_MAX)) {
365 i : LOG(ERROR) << "Invalid block type (" << static_cast<uint32>(type)
366 : << ") and/or attributes ("
367 : << base::StringPrintf("%04X", attributes)
368 : << ") for block with id " << block->id() << ".";
369 i : return false;
370 : }
371 :
372 E : block->type_ = static_cast<BlockGraph::BlockType>(type);
373 E : block->size_ = size;
374 E : block->alignment_ = alignment;
375 E : block->section_ = section;
376 E : block->attributes_ = attributes;
377 :
378 E : return true;
379 E : }
380 :
381 : bool BlockGraphSerializer::SaveBlockLabels(const BlockGraph::Block& block,
382 E : OutArchive* out_archive) const {
383 E : DCHECK(out_archive != NULL);
384 :
385 E : if (has_attributes(BlockGraphSerializer::OMIT_LABELS))
386 i : return true;
387 :
388 E : uint32 count = block.labels().size();
389 E : if (!SaveUint32(count, out_archive)) {
390 i : LOG(ERROR) << "Unable to save label count.";
391 i : return false;
392 : }
393 :
394 : BlockGraph::Block::LabelMap::const_iterator label_iter =
395 E : block.labels().begin();
396 E : for (; label_iter != block.labels().end(); label_iter++) {
397 : COMPILE_ASSERT(BlockGraph::LABEL_ATTRIBUTES_MAX <= (1 << 16),
398 : label_attributes_require_more_than_16_bits);
399 :
400 E : int32 offset = label_iter->first;
401 E : const BlockGraph::Label& label = label_iter->second;
402 E : uint16 attributes = static_cast<uint16>(label.attributes());
403 :
404 : if (!SaveInt32(offset, out_archive) || !out_archive->Save(attributes) ||
405 E : !MaybeSaveString(*this, label.name(), out_archive)) {
406 i : LOG(ERROR) << "Unable to save label at offset "
407 : << label_iter->first << " of block with id "
408 : << block.id() << ".";
409 i : return false;
410 : }
411 E : }
412 :
413 E : return true;
414 E : }
415 :
416 : bool BlockGraphSerializer::LoadBlockLabels(BlockGraph::Block* block,
417 E : InArchive* in_archive) const {
418 E : DCHECK(block != NULL);
419 E : DCHECK(in_archive != NULL);
420 :
421 : // The block shouldn't have any labels yet.
422 E : DCHECK_EQ(0u, block->labels().size());
423 :
424 E : if (has_attributes(BlockGraphSerializer::OMIT_LABELS))
425 i : return true;
426 :
427 E : uint32 label_count = 0;
428 E : if (!LoadUint32(&label_count, in_archive)) {
429 i : LOG(ERROR) << "Unable to load label count.";
430 i : return false;
431 : }
432 :
433 E : for (size_t i = 0; i < label_count; ++i) {
434 E : int32 offset = 0;
435 E : uint16 attributes = 0;
436 E : std::string name;
437 :
438 : if (!LoadInt32(&offset, in_archive) || !(in_archive->Load(&attributes)) ||
439 E : !MaybeLoadString(*this, &name, in_archive)) {
440 i : LOG(ERROR) << "Unable to load label " << i << " of " << label_count
441 : << " for block with id " << block->id() << ".";
442 i : return false;
443 : }
444 :
445 : // Ensure the attributes are valid.
446 E : if (!ValidAttributes(attributes, BlockGraph::LABEL_ATTRIBUTES_MAX)) {
447 i : LOG(ERROR) << "Invalid attributes ("
448 : << base::StringPrintf("%04X", attributes) << ") for block "
449 : << "with id " << block->id() << ".";
450 i : return false;
451 : }
452 :
453 E : BlockGraph::Label label(name, attributes);
454 E : CHECK(block->SetLabel(offset, label));
455 E : }
456 E : DCHECK_EQ(label_count, block->labels().size());
457 :
458 E : return true;
459 E : }
460 :
461 : bool BlockGraphSerializer::SaveBlockData(const BlockGraph::Block& block,
462 E : OutArchive* out_archive) const {
463 E : DCHECK(out_archive != NULL);
464 :
465 : // We always output the data size.
466 E : uint32 data_size = block.data_size();
467 E : if (!SaveUint32(data_size, out_archive)) {
468 i : LOG(ERROR) << "Unable to save block data size for block with id "
469 : << block.id() << ".";
470 i : return false;
471 : }
472 :
473 E : bool output_data = false;
474 :
475 E : if (block.data_size() > 0) {
476 E : switch (data_mode_) {
477 : default:
478 i : NOTREACHED();
479 :
480 : case OUTPUT_NO_DATA: {
481 E : output_data = false;
482 E : break;
483 : }
484 :
485 : case OUTPUT_OWNED_DATA: {
486 E : uint8 owns_data = block.owns_data();
487 E : if (!out_archive->Save(owns_data)) {
488 i : LOG(ERROR) << "Unable to save 'owns_data' field of block with id "
489 : << block.id() << ".";
490 i : return false;
491 : }
492 :
493 E : output_data = block.owns_data();
494 E : break;
495 : }
496 :
497 : case OUTPUT_ALL_DATA: {
498 E : output_data = true;
499 : break;
500 : }
501 : }
502 : }
503 :
504 : // Save the data if we need to.
505 E : if (output_data) {
506 E : DCHECK_LT(0u, block.data_size());
507 E : if (!out_archive->out_stream()->Write(block.data_size(), block.data())) {
508 i : LOG(ERROR) << "Unable to save data for block with id "
509 : << block.id() << ".";
510 i : return false;
511 : }
512 : }
513 :
514 : // No callback? Then do nothing!
515 E : if (save_block_data_callback_.get() == NULL)
516 E : return true;
517 :
518 : // Invoke the callback.
519 E : bool data_already_saved = output_data || block.data_size() == 0;
520 : if (!save_block_data_callback_->Run(data_already_saved,
521 E : block, out_archive)) {
522 i : return false;
523 : }
524 :
525 E : return true;
526 E : }
527 :
528 : bool BlockGraphSerializer::LoadBlockData(BlockGraph::Block* block,
529 E : InArchive* in_archive) const {
530 E : DCHECK(block != NULL);
531 E : DCHECK(in_archive != NULL);
532 E : DCHECK_EQ(0u, block->data_size());
533 E : DCHECK(block->data() == NULL);
534 E : DCHECK(!block->owns_data());
535 :
536 E : uint32 data_size = 0;
537 E : if (!LoadUint32(&data_size, in_archive)) {
538 i : LOG(ERROR) << "Unable to load data size for block with id "
539 : << block->id() << ".";
540 i : return false;
541 : }
542 :
543 : // This indicates whether or not we need to explicitly load the data directly
544 : // from the serialized stream.
545 E : bool data_in_stream = false;
546 :
547 E : if (data_size > 0) {
548 E : switch (data_mode_) {
549 : default:
550 i : NOTREACHED();
551 :
552 : case OUTPUT_NO_DATA: {
553 E : data_in_stream = false;
554 E : break;
555 : }
556 :
557 : case OUTPUT_OWNED_DATA: {
558 E : uint8 owns_data = 0;
559 E : if (!in_archive->Load(&owns_data)) {
560 i : LOG(ERROR) << "Unable to load 'owns_data' field of block with id "
561 : << block->id() << ".";
562 i : return false;
563 : }
564 :
565 : // If we own the data then it must have been serialized to the stream.
566 E : data_in_stream = owns_data != 0;
567 E : break;
568 : }
569 :
570 : case OUTPUT_ALL_DATA: {
571 E : data_in_stream = true;
572 : break;
573 : }
574 : }
575 : }
576 :
577 E : bool callback_needs_to_set_data = !data_in_stream && data_size > 0;
578 :
579 E : if (data_in_stream) {
580 E : DCHECK_LT(0u, data_size);
581 :
582 : // Read the data from the stream.
583 E : block->AllocateData(data_size);
584 E : DCHECK_EQ(data_size, block->data_size());
585 E : DCHECK(block->data() != NULL);
586 E : if (!in_archive->in_stream()->Read(data_size, block->GetMutableData())) {
587 i : LOG(ERROR) << "Unable to read data for block with id "
588 : << block->id() << ".";
589 i : return false;
590 : }
591 : }
592 :
593 E : if (callback_needs_to_set_data) {
594 : // If we didn't explicitly load the data, then we expect the callback to
595 : // do it. We make sure there is one.
596 E : if (load_block_data_callback_.get() == NULL) {
597 i : LOG(ERROR) << "No load block data callback specified.";
598 i : return false;
599 : }
600 : }
601 :
602 : // If there's a callback, invoke it.
603 E : if (load_block_data_callback_.get()) {
604 : if (!load_block_data_callback_->Run(callback_needs_to_set_data,
605 : data_size,
606 : block,
607 E : in_archive)) {
608 i : LOG(ERROR) << "Block data callback failed.";
609 i : return false;
610 : }
611 : }
612 :
613 E : if (data_size > 0 && block->data() == NULL) {
614 i : LOG(ERROR) << "Load block data callback failed to set block data.";
615 i : return false;
616 : }
617 :
618 E : if (block->data_size() != data_size) {
619 i : LOG(ERROR) << "Load block data callback set incorrect data size.";
620 i : return false;
621 : }
622 :
623 E : return true;
624 E : }
625 :
626 : bool BlockGraphSerializer::SaveBlockReferences(const BlockGraph::Block& block,
627 E : OutArchive* out_archive) const {
628 : // Output the number of references for this block.
629 E : if (!out_archive->Save(block.references().size())) {
630 i : LOG(ERROR) << "Unable to save reference count for block with id "
631 : << block.id() << ".";
632 i : return false;
633 : }
634 :
635 : // Output the references as (offset, reference) pairs.
636 : BlockGraph::Block::ReferenceMap::const_iterator it =
637 E : block.references().begin();
638 E : for (; it != block.references().end(); ++it) {
639 E : int32 offset = it->first;
640 : if (!SaveInt32(offset, out_archive) ||
641 E : !SaveReference(it->second, out_archive)) {
642 i : LOG(ERROR) << "Unable to save (offset, reference) pair at offset "
643 : << offset << " of block with id " << block.id() << ".";
644 i : return false;
645 : }
646 E : }
647 :
648 E : return true;
649 E : }
650 :
651 : bool BlockGraphSerializer::LoadBlockReferences(BlockGraph* block_graph,
652 : BlockGraph::Block* block,
653 E : InArchive* in_archive) const {
654 E : DCHECK(block_graph != NULL);
655 E : DCHECK(block != NULL);
656 E : DCHECK(in_archive != NULL);
657 :
658 : // This block should not have any references yet.
659 E : DCHECK_EQ(0u, block->references().size());
660 :
661 E : size_t count = 0;
662 E : if (!in_archive->Load(&count)) {
663 i : LOG(ERROR) << "Unable to load reference count for block with id "
664 : << block->id() << ".";
665 i : return false;
666 : }
667 :
668 E : for (size_t i = 0; i < count; ++i) {
669 E : int32 offset = 0;
670 E : BlockGraph::Reference ref;
671 : if (!LoadInt32(&offset, in_archive) ||
672 E : !LoadReference(block_graph, &ref, in_archive)) {
673 i : LOG(ERROR) << "Unable to load (offset, reference) pair " << i << " of "
674 : << count << " for block with id " << block->id() << ".";
675 i : return false;
676 : }
677 E : DCHECK(ref.referenced() != NULL);
678 :
679 E : if (!block->SetReference(offset, ref)) {
680 i : LOG(ERROR) << "Unable to create block reference at offset " << offset
681 : << " of block with id " << block->id() << ".";
682 i : return false;
683 : }
684 E : }
685 :
686 E : return true;
687 E : }
688 :
689 : bool BlockGraphSerializer::SaveReference(const BlockGraph::Reference& ref,
690 E : OutArchive* out_archive) const {
691 E : DCHECK(ref.referenced() != NULL);
692 E : DCHECK(out_archive != NULL);
693 :
694 : COMPILE_ASSERT(BlockGraph::REFERENCE_TYPE_MAX < 16,
695 : reference_type_requires_more_than_one_nibble);
696 : COMPILE_ASSERT(BlockGraph::Reference::kMaximumSize < 16,
697 : reference_size_requires_more_than_one_nibble);
698 :
699 : // The type and size are each stored as a nibble of one byte.
700 : uint8 type_size = (static_cast<uint8>(ref.type()) << 4) |
701 E : static_cast<uint8>(ref.size());
702 E : int32 offset = ref.offset();
703 : // Most often the offset and the base are identical, so we actually save
704 : // the base as a difference from the offset to encourage smaller values.
705 E : int32 base_delta = ref.base() - ref.offset();
706 :
707 : if (!out_archive->Save(type_size) ||
708 : !out_archive->Save(ref.referenced()->id()) ||
709 E : !SaveInt32(offset, out_archive) || !SaveInt32(base_delta, out_archive)) {
710 i : LOG(ERROR) << "Unable to write reference properties.";
711 i : return false;
712 : }
713 :
714 E : return true;
715 E : }
716 :
717 : bool BlockGraphSerializer::LoadReference(BlockGraph* block_graph,
718 : BlockGraph::Reference* ref,
719 E : InArchive* in_archive) const {
720 E : DCHECK(block_graph != NULL);
721 E : DCHECK(ref != NULL);
722 E : DCHECK(in_archive != NULL);
723 :
724 E : uint8 type_size = 0;
725 E : BlockGraph::BlockId id = 0;
726 E : int32 offset = 0;
727 E : int32 base_delta = 0;
728 :
729 : if (!in_archive->Load(&type_size) || !in_archive->Load(&id) ||
730 E : !LoadInt32(&offset, in_archive) || !LoadInt32(&base_delta, in_archive)) {
731 i : LOG(ERROR) << "Unable to load reference properties.";
732 i : return false;
733 : }
734 :
735 : // The type and size are each stored as a nibble of one byte.
736 E : uint8 type = (type_size >> 4) & 0xF;
737 E : uint8 size = type_size & 0xF;
738 :
739 : if (type >= BlockGraph::REFERENCE_TYPE_MAX ||
740 E : size > BlockGraph::Reference::kMaximumSize) {
741 i : LOG(ERROR) << "Invalid reference type (" << static_cast<uint32>(type)
742 : << ") and/or size (" << static_cast<uint32>(size) << ").";
743 i : return false;
744 : }
745 :
746 E : BlockGraph::Block* referenced = block_graph->GetBlockById(id);
747 E : if (referenced == NULL) {
748 i : LOG(ERROR) << "Unable to find referenced block with id " << id << ".";
749 i : return false;
750 : }
751 :
752 : *ref = BlockGraph::Reference(static_cast<BlockGraph::ReferenceType>(type),
753 E : size, referenced, offset, offset + base_delta);
754 :
755 E : return true;
756 E : }
757 :
758 : // Saves an unsigned 32 bit value. This uses a variable length encoding where
759 : // the first three bits are reserved to indicate the number of bytes required to
760 : // store the value.
761 : bool BlockGraphSerializer::SaveUint32(uint32 value,
762 E : OutArchive* out_archive) const {
763 E : DCHECK(out_archive != NULL);
764 :
765 : // Determine the number of bytes needed in the representation.
766 E : uint32 bytes = 1;
767 E : if (value >= (1 << 29)) {
768 E : bytes = 5;
769 E : } else if (value >= (1 << 21)) {
770 E : bytes = 4;
771 E : } else if (value >= (1 << 13)) {
772 E : bytes = 3;
773 E : } else if (value >= (1 << 5)) {
774 E : bytes = 2;
775 : }
776 :
777 : // Output the value, LSB first. We actually only output 5 bits of the LSB.
778 E : uint8 byte = (value & ((1 << 5) - 1));
779 E : byte |= ((bytes - 1) << 5);
780 E : value >>= 5;
781 E : while (true) {
782 E : if (!out_archive->Save(byte)) {
783 i : LOG(ERROR) << "Unable to write variable-length 32-bit unsigned integer.";
784 i : return false;
785 : }
786 :
787 E : if (--bytes == 0)
788 E : break;
789 :
790 E : byte = value & 0xFF;
791 E : value >>= 8;
792 E : }
793 :
794 E : return true;
795 E : }
796 :
797 : // Loads an unsigned 32-bit value using the encoding discussed in SaveUint32.
798 : bool BlockGraphSerializer::LoadUint32(uint32* value,
799 E : InArchive* in_archive) const {
800 E : DCHECK(value != NULL);
801 E : DCHECK(in_archive != NULL);
802 :
803 E : uint32 temp_value = 0;
804 E : uint32 bytes = 0;
805 E : uint32 position = 0;
806 E : uint8 byte = 0;
807 :
808 E : while (true) {
809 E : if (!in_archive->Load(&byte)) {
810 i : LOG(ERROR) << "Unable to read variable-length 32-bit unsigned integer.";
811 i : return false;
812 : }
813 :
814 : // If we're reading the first byte, we need to read the number of bytes
815 : // remaining from its 3 leading bits.
816 E : if (position == 0) {
817 E : bytes = (byte >> 5) & 0x7;
818 E : temp_value = byte & ((1 << 5) - 1);
819 E : position += 5;
820 E : } else {
821 E : temp_value |= byte << position;
822 E : position += 8;
823 : }
824 :
825 E : if (bytes == 0)
826 E : break;
827 :
828 E : --bytes;
829 E : }
830 :
831 E : *value = temp_value;
832 E : return true;
833 E : }
834 :
835 : // Saves a signed 32-bit value using a variable length encoding. This can
836 : // represent signed values where the magnitude is at most 31-bits. We use a
837 : // simple sign-bit encoding, so there are 2 encodings for 0.
838 : bool BlockGraphSerializer::SaveInt32(int32 value,
839 E : OutArchive* out_archive) const {
840 E : DCHECK(out_archive != NULL);
841 :
842 E : uint32 uvalue = static_cast<uint32>(value < 0 ? -value : value);
843 E : CHECK_GT((1u << 31), uvalue);
844 :
845 : // Add the sign bit as the least significant bit. This allows values near 0
846 : // (positive or negative) to be encoded in as little space as possible.
847 E : uvalue <<= 1;
848 E : if (value < 0)
849 E : uvalue |= 1;
850 :
851 E : if (!SaveUint32(uvalue, out_archive))
852 i : return false;
853 :
854 E : return true;
855 E : }
856 :
857 : bool BlockGraphSerializer::LoadInt32(int32* value,
858 E : InArchive* in_archive) const {
859 E : DCHECK(value != NULL);
860 E : DCHECK(in_archive != NULL);
861 :
862 E : uint32 uvalue = 0;
863 E : if (!LoadUint32(&uvalue, in_archive))
864 i : return false;
865 :
866 E : *value = static_cast<int32>(uvalue >> 1);
867 E : if ((uvalue & 1) != 0)
868 E : *value = -(*value);
869 :
870 E : return true;
871 E : }
872 :
873 : } // namespace block_graph
|