Many Android bootloaders implement the fastboot protocol for loading and flashing images to internal memory (there is some background information about how Android boots and boot image formats in these slides: http://www.slideshare.net/chrissimmonds/android-bootslides20). Fastboot is a simple USB protocol using ASCII text strings for commands and responses. In recent versions of the AOSP you can find the specification in system/core/fastboot/fastboot_protocol.txt.
As an example, this is the interchange when using fastboot to write the recovery image using the command "fastboot flash recovery"
Host->Client "download:004ba00"
Client: "DATA004ba000"
Host: Sends 0x4ba000 (4956160) bytes of raw data
Client:"OKAY"
Host: "flash:recovery"
Client:"OKAY"
You can see this yourself using Wireshark or tcpdump to capture the USB interchange.
Note that there are two stages: first the image is downloaded to the device and then the command "flash" is sent to ask the device to program the data into internal memory. In all bootloader implementations I have seen the image data is buffered in RAM during the download stage and then written out to memory in the flash stage. This means that the image must fit into RAM, which a problem for the system, userdata and cache file system images which are often several times larger than the total amount of RAM. However, these file system images are usually not full, especially in the case of userdata.img which contains very little data initially.
To make the images smaller, and to reduce transfer time, Android generates system.img, userdata.img and cache.img in sparse format. The image is split into chunks of multiples of 4096 bytes. Any chunks that contain no useful data are marked as "Don't care" and no data is sent.
The format is defined in system/core/libsparse/sparse_format.h and looks like this:
The image begins with a sparse_header of 28 bytes, which contains
magic: the number 0xed26ff3a
blk_sz: number of bytes in a block, always 4096
total_blks: number of blocks in the un-sparse file
total_chunks: number of chunks
Each chunk begins with a 12 byte chunk_header, which contains
chunk_type: see below
chunk_sz: number of blocks
There are three chunk types.
CHUNK_TYPE_RAW, followed by chunk_sz blocks of raw data
CHUNK_TYPE_DONT_CARE
CHUNK_TYPE_FILL, followed by 4 bytes of fill data
The last type, CHUNK_TYPE_FILL, fills the chunk with the 4 byte value. I have never seen it used in images produced by a normal AOSP build.
The code for all this is in system/core/libsparse, together with a tool to analyse sparse images: simg_dump.py. Here is an example:
$ system/core/libsparse/simg_dump.py -v out/target/product/manta/cache.img
out/target/product/manta/cache.img: Total of 135168 4096-byte output blocks in 24 input chunks.
input_bytes output_blocks
chunk offset number offset number
1 40 4096 0 1 Raw data
2 4148 4096 1 1 Raw data
3 8256 159744 2 39 Raw data
4 168012 8192 41 2 Raw data
5 176216 1732608 43 423 Raw data
6 1908836 8650752 466 2112 Raw data
7 10559600 4096 2578 1 Raw data
8 10563708 4096 2579 1 Raw data
9 10567816 4096 2580 1 Raw data
10 10571924 0 2581 30187 Don't care
11 10571936 4096 32768 1 Raw data
12 10576044 4096 32769 1 Raw data
13 10580152 0 32770 39 Don't care
14 10580164 8192 32809 2 Raw data
15 10588368 0 32811 32725 Don't care
16 10588380 8192 65536 2 Raw data
17 10596584 0 65538 32766 Don't care
18 10596596 4096 98304 1 Raw data
19 10600704 4096 98305 1 Raw data
20 10604812 0 98306 39 Don't care
21 10604824 8192 98345 2 Raw data
22 10613028 0 98347 32725 Don't care
23 10613040 8192 131072 2 Raw data
24 10621244 0 131074 4094 Don't care
10621244 135168 End
The sparse cache.img is 10621244 bytes (about 10 MiB), but the expanded image is 135168 blocks of 4096, which equals 553648128 bytes (528 MiB), so the sparse file is 1.9% of the size of the full image. Quite a useful saving.
You can tell the AOSP build not to create sparse images by adding this line to your BoardConfig.mk:
TARGET_USERIMAGES_SPARSE_EXT_DISABLED := true
I have added support for sparse images to my U-Boot for BeagleBone Black and removed TARGET_USERIMAGES_SPARSE_EXT_DISABLED from the Android device configuration. Now it takes about 2 minutes to flash the system, userdata and cache images whereas before it used to take 5 minutes.
I have two training courses that will help you:
Android porting: http://www.2net.co.uk/training/android-porting
Android Internals: http://2net.co.uk/training/android-internals