Add a host tool to pack R_ARM_RELATIVE relocations in libchrome.<ver>.so.

tools/relocation_packer/src/relocation_packer_rle.h

Index: tools/relocation_packer/src/relocation_packer_rle.h
diff --git a/tools/relocation_packer/src/relocation_packer_rle.h b/tools/relocation_packer/src/relocation_packer_rle.h
new file mode 100644
index 0000000000000000000000000000000000000000..10e237ee099d69f2d0534635ae654c7f5316b43e
--- /dev/null
+++ b/tools/relocation_packer/src/relocation_packer_rle.h
@@ -0,0 +1,81 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// Run-length encode and decode R_ARM_RELATIVE relocations.
+//
+// R_ARM_RELATIVE relocations are the bulk of dynamic relocations (the
+// .rel.dyn section) in libchrome<version>.so, and the ELF standard
+// representation of them is wasteful.
+//
+// A relocation is 8 bytes (16 bytes on 64 bit plaforms), split into offset
+// and info fields.  Offsets strictly increase, and each is commonly a
+// few bytes different from its predecessor.  There are long runs where
+// the difference does not change.  The info field is always 0x17.  Example,
+// from 'readelf -x4 libchrome.<version>.so':
+//
+//   offset   info     offset   info
+//   808fef01 17000000 848fef01 17000000 ................
+//   888fef01 17000000 8c8fef01 17000000 ................
+//   908fef01 17000000 948fef01 17000000 ................
+//
+// Run length encoding packs this data more efficiently, by representing it
+// as a delta and a count of entries each differing from its predecessor
+// by this delta.  The above can be represented as a start address followed
+// by an encoded count of 6 and offset difference of 4:
+//
+//   start    count    diff
+//   808fef01 00000006 00000004
+//
+// Because R_ARM_RELATIVE relocation offsets strictly increase, the complete
+// set of R_ARM_RELATIVE relocations in libchrome.<version>.so can be
+// represented by a single start address followed by one or more difference
+// and count encoded word pairs:
+//
+//   start    run1 count run1 diff  run2 count run2 diff
+//   808fef01 00000006   00000004   00000010   00000008 ...
+//
+// Decoding regenerates R_ARM_RELATIVE relocations beginning at address
+// 'start' and for each encoded run, incrementing the address by 'difference'
+// for 'count' iterations and emitting a new R_ARM_RELATIVE relocation.
+//
+// Once encoded, data is prefixed by a single word count of packed delta and
+// count pairs.  A final run-length encoded R_ARM_RELATIVE relocations vector
+// might therefore look something like:
+//
+//   pairs    start    run 1             run 2             ... run 15
+//   0000000f 808fef01 00000006 00000004 00000010 00000008 ...
+// Interpreted as:
+//   pairs=15 start=.. count=6,delta=4   count=16,delta=8

[rmcilroy, 2014/06/02 15:16:35]

It seems like this should be applicable to all Elf32_Rel objects, is this right?
 If so, could you make the comments for this class less Arm specific (they can
still give Arm examples, just make it clear it works on all Elf32_Rel objects). 
This can be done in a seperate CL (e.g., for Arm64) if you prefer.

[simonb (inactive), 2014/06/04 16:40:35]

Noted.

+
+#ifndef RELOCATION_PACKER_RLE_H
+#define RELOCATION_PACKER_RLE_H
+
+#include <stdint.h>
+#include <string.h>
+#include <vector>
+
+#include "elf.h"
+
+namespace relocation_packer {
+
+// A RelocationRunLengthCodec packs vectors of R_ARM_RELATIVE relocations
+// into more compact forms, and unpacks them to reproduce the pre-packed data.
+class RelocationRunLengthCodec {
+ public:
+  // Encode R_ARM_RELATIVE relocations into a more compact form.
+  // |relocations| is a vector of R_ARM_RELATIVE relocation structs.
+  // |packed| is the vector of packed words into which relocations are packed.
+  static void Encode(const std::vector<Elf32_Rel>& relocations,
+                     std::vector<Elf32_Word>* packed);
+
+  // Decode R_ARM_RELATIVE relocations from their more compact form.
+  // |packed| is the vector of packed relocations.
+  // |relocations| is a vector of unpacked R_ARM_RELATIVE relocation structs.
+  static void Decode(const std::vector<Elf32_Word>& packed,
+                     std::vector<Elf32_Rel>* relocations);
+};
+
+}  // namespace relocation_packer
+
+#endif  // RELOCATION_PACKER_PACKER_H