diff --git a/rust/treedirstate/Cargo.lock b/rust/treedirstate/Cargo.lock
--- a/rust/treedirstate/Cargo.lock
+++ b/rust/treedirstate/Cargo.lock
@@ -206,6 +206,7 @@
  "itertools 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "quickcheck 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "tempdir 0.3.5 (registry+https://github.com/rust-lang/crates.io-index)",
+ "vlqencoding 0.1.0",
 ]
 
 [[package]]
@@ -239,6 +240,10 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[package]]
+name = "vlqencoding"
+version = "0.1.0"
+
+[[package]]
 name = "winapi"
 version = "0.2.8"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/rust/treedirstate/Cargo.toml b/rust/treedirstate/Cargo.toml
--- a/rust/treedirstate/Cargo.toml
+++ b/rust/treedirstate/Cargo.toml
@@ -13,6 +13,7 @@
 [dependencies]
 byteorder = "*"
 error-chain = "*"
+vlqencoding = { version = "*", path = "../vlqencoding" }
 
 [dev-dependencies]
 itertools = "0.7.2"
diff --git a/rust/treedirstate/src/filestate.rs b/rust/treedirstate/src/filestate.rs
--- a/rust/treedirstate/src/filestate.rs
+++ b/rust/treedirstate/src/filestate.rs
@@ -1,10 +1,11 @@
 // Copyright Facebook, Inc. 2017
 //! File State.
 
-use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
+use byteorder::{ReadBytesExt, WriteBytesExt};
 use errors::*;
 use std::io::{Read, Write};
 use tree::Storable;
+use vlqencoding::{VLQDecode, VLQEncode};
 
 /// Information relating to a file in the dirstate.
 #[derive(Debug, PartialEq, Copy, Clone)]
@@ -38,20 +39,20 @@
 
 impl Storable for FileState {
     /// Write a file entry to the store.
-    fn write(&self, w: &mut Write) -> Result<()> {
+    fn write(&self, mut w: &mut Write) -> Result<()> {
         w.write_u8(self.state)?;
-        w.write_u32::<BigEndian>(self.mode)?;
-        w.write_i32::<BigEndian>(self.size)?;
-        w.write_i32::<BigEndian>(self.mtime)?;
+        w.write_vlq(self.mode)?;
+        w.write_vlq(self.size)?;
+        w.write_vlq(self.mtime)?;
         Ok(())
     }
 
     /// Read an entry from the store.
-    fn read(r: &mut Read) -> Result<FileState> {
+    fn read(mut r: &mut Read) -> Result<FileState> {
         let state = r.read_u8()?;
-        let mode = r.read_u32::<BigEndian>()?;
-        let size = r.read_i32::<BigEndian>()?;
-        let mtime = r.read_i32::<BigEndian>()?;
+        let mode = r.read_vlq()?;
+        let size = r.read_vlq()?;
+        let mtime = r.read_vlq()?;
         Ok(FileState {
             state,
             mode,
diff --git a/rust/treedirstate/src/lib.rs b/rust/treedirstate/src/lib.rs
--- a/rust/treedirstate/src/lib.rs
+++ b/rust/treedirstate/src/lib.rs
@@ -31,6 +31,8 @@
 #[cfg(test)]
 extern crate tempdir;
 
+extern crate vlqencoding;
+
 pub mod dirstate;
 pub mod errors;
 pub mod filestate;
diff --git a/rust/treedirstate/src/tree.rs b/rust/treedirstate/src/tree.rs
--- a/rust/treedirstate/src/tree.rs
+++ b/rust/treedirstate/src/tree.rs
@@ -1,12 +1,13 @@
 // Copyright Facebook, Inc. 2017
 //! Directory State Tree.
 
-use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
+use byteorder::{ReadBytesExt, WriteBytesExt};
 use errors::*;
 use std::collections::Bound;
 use std::io::{Cursor, Read, Write};
 use store::{BlockId, Store, StoreView};
 use vecmap::VecMap;
+use vlqencoding::{VLQDecode, VLQEncode};
 
 /// Trait that must be implemented by types that can be stored as the value in the tree.
 pub trait Storable
@@ -82,29 +83,29 @@
 
 impl<T: Storable + Clone> NodeEntry<T> {
     /// Read an entry from the store.  Returns the name and the entry.
-    fn read(r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
+    fn read(mut r: &mut Read) -> Result<(Key, NodeEntry<T>)> {
         let entry_type = r.read_u8()?;
         match entry_type {
             b'f' => {
                 // File entry.
                 let data = T::read(r)?;
-                let name_len = r.read_u32::<BigEndian>()?;
-                let mut name = Vec::with_capacity(name_len as usize);
+                let name_len = r.read_vlq()?;
+                let mut name = Vec::with_capacity(name_len);
                 unsafe {
                     // Safe as we've just allocated the buffer and are about to read into it.
-                    name.set_len(name_len as usize);
+                    name.set_len(name_len);
                 }
                 r.read_exact(name.as_mut_slice())?;
                 Ok((name, NodeEntry::File(data)))
             }
             b'd' => {
                 // Directory entry.
-                let id = r.read_u64::<BigEndian>()?;
-                let name_len = r.read_u32::<BigEndian>()?;
-                let mut name = Vec::with_capacity(name_len as usize);
+                let id = r.read_vlq()?;
+                let name_len = r.read_vlq()?;
+                let mut name = Vec::with_capacity(name_len);
                 unsafe {
                     // Safe as we've just allocated the buffer and are about to read into it.
-                    name.set_len(name_len as usize);
+                    name.set_len(name_len);
                 }
                 r.read_exact(name.as_mut_slice())?;
                 Ok((name, NodeEntry::Directory(Node::open(BlockId(id)))))
@@ -146,7 +147,7 @@
         let data = store.read(id)?;
         let len = data.len() as u64;
         let mut cursor = Cursor::new(data);
-        let count = cursor.read_u32::<BigEndian>()? as usize;
+        let count = cursor.read_vlq()?;
         let mut entries = NodeEntryMap::with_capacity(count);
         while cursor.position() < len {
             let (name, entry) = NodeEntry::read(&mut cursor)?;
@@ -173,7 +174,7 @@
         let entries = self.entries
             .as_mut()
             .expect("Node should have entries populated before writing out.");
-        data.write_u32::<BigEndian>(entries.len() as u32)?;
+        data.write_vlq(entries.len())?;
         for (name, entry) in entries.iter_mut() {
             match entry {
                 &mut NodeEntry::File(ref file) => {
@@ -182,10 +183,10 @@
                 }
                 &mut NodeEntry::Directory(ref mut node) => {
                     data.write_u8(b'd')?;
-                    data.write_u64::<BigEndian>(node.id.unwrap().0)?;
+                    data.write_vlq(node.id.unwrap().0)?;
                 }
             }
-            data.write_u32::<BigEndian>(name.len() as u32)?;
+            data.write_vlq(name.len())?;
             data.write(name)?;
         }
         self.id = Some(store.append(&data)?);