new image diffing tool and support for image patches in applypatch

Images (like boot and recovery) consist of large sections of gzipped
data interspersed with other data.  To do effective binary patching of
these files, we need to apply patches to the gzipped parts in
'uncompressed space', that is, we decompress, apply a patch, then
recompress to obtain the desired output.

This change defines a new format with these patches, which is
basically a description of how the source and target files are to be
divided up into chunks and a bsdiff patch for each chunk.  We add a
new host executable, "imgdiff", for generating these patches from
source and target images, and add support in applypatch for
recognizing this format and applying it on the device.
diff --git a/tools/applypatch/Android.mk b/tools/applypatch/Android.mk
index 09f9862..3956ea6 100644
--- a/tools/applypatch/Android.mk
+++ b/tools/applypatch/Android.mk
@@ -12,18 +12,29 @@
 # See the License for the specific language governing permissions and
 # limitations under the License.
 
+ifneq ($(TARGET_SIMULATOR),true)
+
 LOCAL_PATH := $(call my-dir)
 include $(CLEAR_VARS)
 
-ifneq ($(TARGET_SIMULATOR),true)
-
-LOCAL_SRC_FILES := applypatch.c bsdiff.c freecache.c
+LOCAL_SRC_FILES := applypatch.c bsdiff.c freecache.c imgpatch.c
 LOCAL_MODULE := applypatch
 LOCAL_FORCE_STATIC_EXECUTABLE := true
 LOCAL_MODULE_TAGS := eng
-LOCAL_C_INCLUDES += external/bzip2
-LOCAL_STATIC_LIBRARIES += libmincrypt libbz libc
+LOCAL_C_INCLUDES += external/bzip2 external/zlib
+LOCAL_STATIC_LIBRARIES += libmincrypt libbz libz libc
 
 include $(BUILD_EXECUTABLE)
 
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := imgdiff.c
+LOCAL_MODULE := imgdiff
+LOCAL_FORCE_STATIC_EXECUTABLE := true
+LOCAL_MODULE_TAGS := eng
+LOCAL_C_INCLUDES += external/zlib
+LOCAL_STATIC_LIBRARIES += libz
+
+include $(BUILD_HOST_EXECUTABLE)
+
 endif  # !TARGET_SIMULATOR