From: Ken Sumrall <ksumrall@android.com>
Date: Tue, 17 Aug 2010 02:17:38 +0000 (-0700)
Subject: Add support for IEEE 802.c stylc CRC32 computation to the sparse image tools
X-Git-Tag: android-x86-4.4-r1~279^2
X-Git-Url: http://git.osdn.net/view?p=android-x86%2Fsystem-extras.git;a=commitdiff_plain;h=5a6181798de5c2d882c79b27406c330a6fa7da3e

Add support for IEEE 802.c stylc CRC32 computation to the sparse image tools

Add support for computing the CRC32 of the data when we make a sparse image,
and storing that CRC in the header.  Also update the simg2img tool that reads
sparse images to compute the CRC32 as it writes the image, and check to make
sure it matches what's in the header.

Change-Id: Iadea3a760f91fa9b1efd22a3580dd1943b1ff52e
---

diff --git a/ext4_utils/Android.mk b/ext4_utils/Android.mk
index 14702540..c7934a3d 100644
--- a/ext4_utils/Android.mk
+++ b/ext4_utils/Android.mk
@@ -14,6 +14,7 @@ libext4_utils_src_files := \
         indirect.c \
         uuid.c \
         sha1.c \
+	sparse_crc32.c
 
 LOCAL_SRC_FILES := $(libext4_utils_src_files)
 LOCAL_MODULE := libext4_utils
@@ -63,7 +64,8 @@ include $(BUILD_HOST_EXECUTABLE)
 
 include $(CLEAR_VARS)
 
-LOCAL_SRC_FILES := simg2img.c
+LOCAL_SRC_FILES := simg2img.c \
+	sparse_crc32.c
 LOCAL_MODULE := simg2img
 
 include $(BUILD_HOST_EXECUTABLE)
diff --git a/ext4_utils/output_file.c b/ext4_utils/output_file.c
index 2705701c..3785b06e 100644
--- a/ext4_utils/output_file.c
+++ b/ext4_utils/output_file.c
@@ -27,6 +27,7 @@
 #include "ext4_utils.h"
 #include "output_file.h"
 #include "sparse_format.h"
+#include "sparse_crc32.h"
 
 #if defined(__APPLE__) && defined(__MACH__)
 #define lseek64 lseek
@@ -148,7 +149,7 @@ static u8 *zero_buf;
 static int emit_skip_chunk(struct output_file *out, u64 skip_len)
 {
 	chunk_header_t chunk_header;
-	int ret;
+	int ret, chunk;
 
 	//DBG printf("skip chunk: 0x%llx bytes\n", skip_len);
 
@@ -166,10 +167,17 @@ static int emit_skip_chunk(struct output_file *out, u64 skip_len)
 	ret = out->ops->write(out, (u8 *)&chunk_header, sizeof(chunk_header));
 	if (ret < 0)
 		return -1;
-	// KEN: TODO: CRC computation
+
 	out->cur_out_ptr += skip_len;
 	out->chunk_cnt++;
 
+	/* Compute the CRC for all those zeroes.  Do it block_size bytes at a time. */
+	while (skip_len) {
+		chunk = (skip_len > info.block_size) ? info.block_size : skip_len;
+		out->crc32 = sparse_crc32(out->crc32, zero_buf, chunk);
+		skip_len -= chunk;
+	}
+
 	return 0;
 }
 
@@ -231,7 +239,9 @@ static int write_chunk_raw(struct output_file *out, u64 off, u8 *data, int len)
 			return -1;
 	}
 
-	// KEN: TODO: CRC computation of both the raw data and and zero buf data written */
+	out->crc32 = sparse_crc32(out->crc32, data, len);
+	if (zero_len)
+		out->crc32 = sparse_crc32(out->crc32, zero_buf, zero_len);
 	out->cur_out_ptr += rnd_up_len;
 	out->chunk_cnt++;
 
@@ -293,6 +303,10 @@ struct output_file *open_output_file(const char *filename, int gz, int sparse)
 	out->sparse = sparse;
 	out->cur_out_ptr = 0ll;
 	out->chunk_cnt = 0;
+
+	/* Initialize the crc32 value */
+	out->crc32 = 0;
+
 	if (out->sparse) {
 		/* Write out the file header.  We'll update the unknown fields
 		 * when we close the file.
@@ -321,7 +335,6 @@ void pad_output_file(struct output_file *out, u64 len)
 		 * cur_out_ptr is not already at the end of the filesystem.
 		 * We also need to compute the CRC for it.
 		 */
-		 //KEN: TODO: CRC computation!
 		if (len < out->cur_out_ptr) {
 			error("attempted to pad file %llu bytes less than the current output pointer",
 					out->cur_out_ptr - len);
diff --git a/ext4_utils/simg2img.c b/ext4_utils/simg2img.c
index 9c1ad370..88c67b48 100644
--- a/ext4_utils/simg2img.c
+++ b/ext4_utils/simg2img.c
@@ -27,6 +27,7 @@
 #include "ext4_utils.h"
 #include "output_file.h"
 #include "sparse_format.h"
+#include "sparse_crc32.h"
 
 #if defined(__APPLE__) && defined(__MACH__)
 #define lseek64 lseek
@@ -36,6 +37,9 @@
 #define COPY_BUF_SIZE (1024*1024)
 u8 *copybuf;
 
+/* This will be malloc'ed with the size of blk_sz from the sparse file header */
+u8* zerobuf;
+
 #define SPARSE_HEADER_MAJOR_VER 1
 #define SPARSE_HEADER_LEN       (sizeof(sparse_header_t))
 #define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
@@ -52,8 +56,15 @@ int process_raw_chunk(FILE *in, FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
 
 	while (len) {
 		chunk = (len > COPY_BUF_SIZE) ? COPY_BUF_SIZE : len;
-		fread(copybuf, chunk, 1, in);
-		fwrite(copybuf, chunk, 1, out);
+		if (fread(copybuf, chunk, 1, in) != 1) {
+			fprintf(stderr, "fread returned an error copying a raw chunk\n");
+			exit(-1);
+		}
+		*crc32 = sparse_crc32(*crc32, copybuf, chunk);
+		if (fwrite(copybuf, chunk, 1, out) != 1) {
+			fprintf(stderr, "fwrite returned an error copying a raw chunk\n");
+			exit(-1);
+		}
 		len -= chunk;
 	}
 
@@ -67,17 +78,26 @@ int process_skip_chunk(FILE *out, u32 blocks, u32 blk_sz, u32 *crc32)
 	 * as a 32 bit value of blocks.
 	 */
 	u64 len = (u64)blocks * blk_sz;
-	long skip_chunk;
+	u64 len_save;
+	u32 skip_chunk;
 
 	/* Fseek takes the offset as a long, which may be 32 bits on some systems.
 	 * So, lets do a sequence of fseeks() with SEEK_CUR to get the file pointer
 	 * where we want it.
 	 */
+	len_save = len;
 	while (len) {
 		skip_chunk = (len > 0x80000000) ? 0x80000000 : len;
 		fseek(out, skip_chunk, SEEK_CUR);
 		len -= skip_chunk;
 	}
+	/* And compute the CRC of the skipped region a chunk at a time */
+	len = len_save;
+	while (len) {
+		skip_chunk = (skip_chunk > blk_sz) ? blk_sz : skip_chunk;
+		*crc32 = sparse_crc32(*crc32, zerobuf, skip_chunk);
+		len -= skip_chunk;
+	}
 
 	return blocks;
 }
@@ -133,6 +153,11 @@ int main(int argc, char *argv[])
 		fseek(in, sparse_header.file_hdr_sz - SPARSE_HEADER_LEN, SEEK_CUR);
 	}
 
+	if ( (zerobuf = malloc(sparse_header.blk_sz)) == 0) {
+		fprintf(stderr, "Cannot malloc zero buf\n");
+		exit(-1);
+	}
+
 	for (i=0; i<sparse_header.total_chunks; i++) {
 		if (fread(&chunk_header, sizeof(chunk_header), 1, in) != 1) {
 			fprintf(stderr, "Error reading chunk header\n");
@@ -176,7 +201,10 @@ int main(int argc, char *argv[])
 	 * will make the file the correct size.  Make sure the offset is
 	 * computed in 64 bits, and the function called can handle 64 bits.
 	 */
-	ftruncate(fileno(out), (u64)total_blocks * sparse_header.blk_sz);
+	if (ftruncate(fileno(out), (u64)total_blocks * sparse_header.blk_sz)) {
+		fprintf(stderr, "Error calling ftruncate() to set the image size\n");
+		exit(-1);
+	}
 
 	fclose(in);
 	fclose(out);
@@ -188,7 +216,7 @@ int main(int argc, char *argv[])
 	}
 
 	if (sparse_header.image_checksum != crc32) {
-		fprintf(stderr, "computed crc32 of %d, expected %d\n",
+		fprintf(stderr, "computed crc32 of 0x%8.8x, expected 0x%8.8x\n",
 			 crc32, sparse_header.image_checksum);
 		exit(-1);
 	}
diff --git a/ext4_utils/sparse_crc32.c b/ext4_utils/sparse_crc32.c
new file mode 100644
index 00000000..9336b1d8
--- /dev/null
+++ b/ext4_utils/sparse_crc32.c
@@ -0,0 +1,111 @@
+/*-
+ *  COPYRIGHT (C) 1986 Gary S. Brown.  You may use this program, or
+ *  code or tables extracted from it, as desired without restriction.
+ */
+
+/*
+ *  First, the polynomial itself and its table of feedback terms.  The
+ *  polynomial is
+ *  X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
+ *
+ *  Note that we take it "backwards" and put the highest-order term in
+ *  the lowest-order bit.  The X^32 term is "implied"; the LSB is the
+ *  X^31 term, etc.  The X^0 term (usually shown as "+1") results in
+ *  the MSB being 1
+ *
+ *  Note that the usual hardware shift register implementation, which
+ *  is what we're using (we're merely optimizing it by doing eight-bit
+ *  chunks at a time) shifts bits into the lowest-order term.  In our
+ *  implementation, that means shifting towards the right.  Why do we
+ *  do it this way?  Because the calculated CRC must be transmitted in
+ *  order from highest-order term to lowest-order term.  UARTs transmit
+ *  characters in order from LSB to MSB.  By storing the CRC this way
+ *  we hand it to the UART in the order low-byte to high-byte; the UART
+ *  sends each low-bit to hight-bit; and the result is transmission bit
+ *  by bit from highest- to lowest-order term without requiring any bit
+ *  shuffling on our part.  Reception works similarly
+ *
+ *  The feedback terms table consists of 256, 32-bit entries.  Notes
+ *
+ *      The table can be generated at runtime if desired; code to do so
+ *      is shown later.  It might not be obvious, but the feedback
+ *      terms simply represent the results of eight shift/xor opera
+ *      tions for all combinations of data and CRC register values
+ *
+ *      The values must be right-shifted by eight bits by the "updcrc
+ *      logic; the shift must be unsigned (bring in zeroes).  On some
+ *      hardware you could probably optimize the shift in assembler by
+ *      using byte-swap instructions
+ *      polynomial $edb88320
+ *
+ *
+ * CRC32 code derived from work by Gary S. Brown.
+ */
+
+/* Code taken from FreeBSD 8 */
+#include "ext4_utils.h"
+
+static u32 crc32_tab[] = {
+        0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
+        0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+        0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
+        0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+        0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
+        0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+        0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
+        0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+        0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
+        0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+        0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
+        0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+        0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
+        0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+        0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
+        0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+        0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
+        0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+        0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
+        0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+        0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
+        0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+        0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
+        0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+        0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
+        0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+        0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
+        0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+        0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
+        0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+        0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
+        0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+        0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
+        0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+        0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
+        0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+        0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
+        0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+        0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
+        0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+        0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
+        0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+        0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
+};
+
+/*
+ * A function that calculates the CRC-32 based on the table above is
+ * given below for documentation purposes. An equivalent implementation
+ * of this function that's actually used in the kernel can be found
+ * in sys/libkern.h, where it can be inlined.
+ */
+
+u32 sparse_crc32(u32 crc_in, const void *buf, int size)
+{
+        const u8 *p = buf;
+        u32 crc;
+
+        crc = crc_in ^ ~0U;
+        while (size--)
+                crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
+        return crc ^ ~0U;
+}
+
diff --git a/ext4_utils/sparse_crc32.h b/ext4_utils/sparse_crc32.h
new file mode 100644
index 00000000..21625bac
--- /dev/null
+++ b/ext4_utils/sparse_crc32.h
@@ -0,0 +1,18 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+u32 sparse_crc32(u32 crc, const void *buf, size_t size);
+