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