hash-object: How Git Identifies Content

Strip away branches, remotes, staging and merges and git is one idea: name every piece of content by the hash of the content itself. After this lesson your program turns any text into the exact 40-character name real git gives it as a file object (a blob), and every later lesson builds on that naming function.

Content addressing

A hash function maps any bytes to a fixed-size fingerprint. Git uses SHA-1: 160 bits, written as 40 lowercase hex characters. The same input gives the same hash on every machine, and changing one byte gives an unrelated hash, so the hash can serve as the name.

• Deduplication is free. A thousand files with identical content hash to one name and are stored once.
• Integrity is built in. If a disk flips a bit, the content no longer matches its name, and git notices every time it reads the object.
• Comparing is trivial. Two repositories compare what they hold by comparing names, with no timestamps and no central authority.

The blob format: header, NUL, bytes

Git does not hash a file's bytes raw. It first puts a header in front:

blob <size-in-bytes> NUL <content>

A full trace on a string this lesson's exercise does not use. The content is what is up, doc?, which is 16 bytes:

content  : 77 68 61 74 20 69 73 20 75 70 2c 20 64 6f 63 3f     (16 bytes)
header   : 62 6c 6f 62 20 31 36 00                              "blob 16" then one zero byte
hashed   : header followed by content                            24 bytes in all
SHA-1    : bd9dbf5aae1a3862dd1526723246b20206e5fc37

You can check any answer against real git, which must agree with you byte for byte. printf writes no trailing newline, which is why it is used here and echo is not:

$ printf 'what is up, doc?' | git hash-object --stdin
bd9dbf5aae1a3862dd1526723246b20206e5fc37

The header makes every object self-describing: given an object's bytes you know its type and where it ends without any outside bookkeeping. It also keeps a blob and a commit that happen to contain identical text from ever colliding, because their headers differ.

Size means bytes

The number in the header is the byte length of the content, not the number of characters and not the length of the header. The text héllo has 5 characters, but é takes 2 bytes in UTF-8, so its blob header says blob 6. A program that counts characters computes a valid-looking hash that matches nothing in the world. Decimal digits are written without padding: blob 9, blob 10, blob 100.

A blob has no name

A blob is content and nothing else: no filename, no permissions, no timestamp, no author. README.md and LICENSE with identical text are one blob. Names and modes live one level up, in tree objects, two chapters from now. Separating the two is what makes renames cheap and deduplication total.

Common mistakes

• Hashing the content without the header, or with the header but no zero byte. Either gives a plausible-looking 40 characters that is wrong.
• Writing the separator as the two characters backslash and zero instead of one byte with value 0.
• Using the character count for a line with non-ASCII text. héllo must say 6.
• Letting a trailing newline into the content. In this exercise the newline that ends an input line is not part of the file.
• Dropping blank lines. An empty line is an empty file, which has a real hash that git shows in every repository that ever committed an empty file.

Your exercise

Each input line is one file's content. Print the blob hash of each line, one per output line. The starter already reads the input and prints your result; you write hash_blob. The single most likely mistake is the byte-versus-character count, so test a line with an accented letter before you submit.

Rust, C and C++ graders compile a single file with the standard library only, with no sha1 crate and no OpenSSL. Those starters ship a sha1_hex function for you, and later lessons that need a hash ship the same one.