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]
 tempdir = "*"
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::{VLQEncode, VLQDecode};
 
 /// Information relating to a file in the dirstate.
 #[derive(Debug, PartialEq, Clone)]
@@ -28,20 +29,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 as u8)?;
-        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()? as char;
-        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
@@ -23,6 +23,8 @@
 #[macro_use]
 extern crate cpython;
 
+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,13 +1,14 @@
 // Copyright Facebook, Inc. 2017
 //! Directory State Tree.
 
-use byteorder::{BigEndian, ReadBytesExt, WriteBytesExt};
+use byteorder::{ReadBytesExt, WriteBytesExt};
 use errors::*;
 use std::clone::Clone;
 use std::collections::Bound;
 use std::io::{Cursor, Read, Write};
 use store::{BlockId, Store, StoreView};
 use vecmap::VecMap;
+use vlqencoding::{VLQEncode, VLQDecode};
 
 /// Item that can be stored in a tree.
 pub trait Storable
@@ -79,29 +80,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>()? as usize;
-                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(id))))
@@ -143,7 +144,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 = NodeEntryList::with_capacity(count);
             while cursor.position() < len {
                 let (name, entry) = NodeEntry::read(&mut cursor)?;
@@ -168,7 +169,7 @@
     fn write_entries(&mut self, store: &mut Store) -> Result<()> {
         let mut data = Vec::new();
         if let Some(ref mut entries) = self.entries {
-            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) => {
@@ -177,10 +178,10 @@
                     }
                     &mut NodeEntry::Directory(ref mut node) => {
                         data.write_u8(b'd')?;
-                        data.write_u64::<BigEndian>(node.id.unwrap() as u64)?;
+                        data.write_vlq(node.id.unwrap())?;
                     }
                 }
-                data.write_u32::<BigEndian>(name.len() as u32)?;
+                data.write_vlq(name.len())?;
                 data.write(name)?;
             }
         } else {