diff --git a/applypatch/Android.mk b/applypatch/Android.mk
index bdaef1b..47ddad6 100644
--- a/applypatch/Android.mk
+++ b/applypatch/Android.mk
@@ -33,6 +33,7 @@
     libotafault \
     libbase \
     libcrypto \
+    libbspatch \
     libbz \
     libz
 LOCAL_CFLAGS := \
@@ -54,6 +55,7 @@
 LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
 LOCAL_STATIC_LIBRARIES := \
     libcrypto \
+    libbspatch \
     libbz \
     libz
 LOCAL_CFLAGS := \
@@ -76,6 +78,7 @@
 LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
 LOCAL_STATIC_LIBRARIES := \
     libcrypto \
+    libbspatch \
     libbz \
     libz
 LOCAL_CFLAGS := \
@@ -111,6 +114,7 @@
     libedify \
     libotafault \
     libcrypto \
+    libbspatch \
     libbz
 LOCAL_SHARED_LIBRARIES := \
     libbase \
diff --git a/applypatch/bspatch.cpp b/applypatch/bspatch.cpp
index eb45e9c..9920c2b 100644
--- a/applypatch/bspatch.cpp
+++ b/applypatch/bspatch.cpp
@@ -21,16 +21,12 @@
 // notice.
 
 #include <stdio.h>
-#include <sys/stat.h>
 #include <sys/types.h>
-#include <errno.h>
-#include <unistd.h>
-#include <string.h>
 
-#include <bzlib.h>
+#include <bspatch.h>
 
-#include "openssl/sha.h"
 #include "applypatch/applypatch.h"
+#include "openssl/sha.h"
 
 void ShowBSDiffLicense() {
     puts("The bsdiff library used herein is:\n"
@@ -64,183 +60,25 @@
         );
 }
 
-static off_t offtin(const u_char *buf)
-{
-    off_t y;
-
-    y=buf[7]&0x7F;
-    y=y*256;y+=buf[6];
-    y=y*256;y+=buf[5];
-    y=y*256;y+=buf[4];
-    y=y*256;y+=buf[3];
-    y=y*256;y+=buf[2];
-    y=y*256;y+=buf[1];
-    y=y*256;y+=buf[0];
-
-    if(buf[7]&0x80) y=-y;
-
-    return y;
+int ApplyBSDiffPatch(const unsigned char* old_data, ssize_t old_size, const Value* patch,
+                     ssize_t patch_offset, SinkFn sink, void* token, SHA_CTX* ctx) {
+  auto sha_sink = [&](const uint8_t* data, size_t len) {
+    len = sink(data, len, token);
+    if (ctx) SHA1_Update(ctx, data, len);
+    return len;
+  };
+  return bsdiff::bspatch(old_data, old_size,
+                         reinterpret_cast<const uint8_t*>(&patch->data[patch_offset]),
+                         patch->data.size(), sha_sink);
 }
 
-int FillBuffer(unsigned char* buffer, int size, bz_stream* stream) {
-    stream->next_out = (char*)buffer;
-    stream->avail_out = size;
-    while (stream->avail_out > 0) {
-        int bzerr = BZ2_bzDecompress(stream);
-        if (bzerr != BZ_OK && bzerr != BZ_STREAM_END) {
-            printf("bz error %d decompressing\n", bzerr);
-            return -1;
-        }
-        if (stream->avail_out > 0) {
-            printf("need %d more bytes\n", stream->avail_out);
-        }
-    }
-    return 0;
-}
-
-int ApplyBSDiffPatch(const unsigned char* old_data, ssize_t old_size,
-                     const Value* patch, ssize_t patch_offset,
-                     SinkFn sink, void* token, SHA_CTX* ctx) {
-
-    std::vector<unsigned char> new_data;
-    if (ApplyBSDiffPatchMem(old_data, old_size, patch, patch_offset, &new_data) != 0) {
-        return -1;
-    }
-
-    if (sink(new_data.data(), new_data.size(), token) < static_cast<ssize_t>(new_data.size())) {
-        printf("short write of output: %d (%s)\n", errno, strerror(errno));
-        return 1;
-    }
-    if (ctx) SHA1_Update(ctx, new_data.data(), new_data.size());
-    return 0;
-}
-
-int ApplyBSDiffPatchMem(const unsigned char* old_data, ssize_t old_size,
-                        const Value* patch, ssize_t patch_offset,
-                        std::vector<unsigned char>* new_data) {
-    // Patch data format:
-    //   0       8       "BSDIFF40"
-    //   8       8       X
-    //   16      8       Y
-    //   24      8       sizeof(newfile)
-    //   32      X       bzip2(control block)
-    //   32+X    Y       bzip2(diff block)
-    //   32+X+Y  ???     bzip2(extra block)
-    // with control block a set of triples (x,y,z) meaning "add x bytes
-    // from oldfile to x bytes from the diff block; copy y bytes from the
-    // extra block; seek forwards in oldfile by z bytes".
-
-    const unsigned char* header = reinterpret_cast<const unsigned char*>(&patch->data[patch_offset]);
-    if (memcmp(header, "BSDIFF40", 8) != 0) {
-        printf("corrupt bsdiff patch file header (magic number)\n");
-        return 1;
-    }
-
-    ssize_t ctrl_len, data_len, new_size;
-    ctrl_len = offtin(header+8);
-    data_len = offtin(header+16);
-    new_size = offtin(header+24);
-
-    if (ctrl_len < 0 || data_len < 0 || new_size < 0) {
-        printf("corrupt patch file header (data lengths)\n");
-        return 1;
-    }
-
-    int bzerr;
-
-    bz_stream cstream;
-    cstream.next_in = const_cast<char*>(&patch->data[patch_offset + 32]);
-    cstream.avail_in = ctrl_len;
-    cstream.bzalloc = NULL;
-    cstream.bzfree = NULL;
-    cstream.opaque = NULL;
-    if ((bzerr = BZ2_bzDecompressInit(&cstream, 0, 0)) != BZ_OK) {
-        printf("failed to bzinit control stream (%d)\n", bzerr);
-    }
-
-    bz_stream dstream;
-    dstream.next_in = const_cast<char*>(&patch->data[patch_offset + 32 + ctrl_len]);
-    dstream.avail_in = data_len;
-    dstream.bzalloc = NULL;
-    dstream.bzfree = NULL;
-    dstream.opaque = NULL;
-    if ((bzerr = BZ2_bzDecompressInit(&dstream, 0, 0)) != BZ_OK) {
-        printf("failed to bzinit diff stream (%d)\n", bzerr);
-    }
-
-    bz_stream estream;
-    estream.next_in = const_cast<char*>(&patch->data[patch_offset + 32 + ctrl_len + data_len]);
-    estream.avail_in = patch->data.size() - (patch_offset + 32 + ctrl_len + data_len);
-    estream.bzalloc = NULL;
-    estream.bzfree = NULL;
-    estream.opaque = NULL;
-    if ((bzerr = BZ2_bzDecompressInit(&estream, 0, 0)) != BZ_OK) {
-        printf("failed to bzinit extra stream (%d)\n", bzerr);
-    }
-
-    new_data->resize(new_size);
-
-    off_t oldpos = 0, newpos = 0;
-    off_t ctrl[3];
-    int i;
-    unsigned char buf[24];
-    while (newpos < new_size) {
-        // Read control data
-        if (FillBuffer(buf, 24, &cstream) != 0) {
-            printf("error while reading control stream\n");
-            return 1;
-        }
-        ctrl[0] = offtin(buf);
-        ctrl[1] = offtin(buf+8);
-        ctrl[2] = offtin(buf+16);
-
-        if (ctrl[0] < 0 || ctrl[1] < 0) {
-            printf("corrupt patch (negative byte counts)\n");
-            return 1;
-        }
-
-        // Sanity check
-        if (newpos + ctrl[0] > new_size) {
-            printf("corrupt patch (new file overrun)\n");
-            return 1;
-        }
-
-        // Read diff string
-        if (FillBuffer(new_data->data() + newpos, ctrl[0], &dstream) != 0) {
-            printf("error while reading diff stream\n");
-            return 1;
-        }
-
-        // Add old data to diff string
-        for (i = 0; i < ctrl[0]; ++i) {
-            if ((oldpos+i >= 0) && (oldpos+i < old_size)) {
-                (*new_data)[newpos+i] += old_data[oldpos+i];
-            }
-        }
-
-        // Adjust pointers
-        newpos += ctrl[0];
-        oldpos += ctrl[0];
-
-        // Sanity check
-        if (newpos + ctrl[1] > new_size) {
-            printf("corrupt patch (new file overrun)\n");
-            return 1;
-        }
-
-        // Read extra string
-        if (FillBuffer(new_data->data() + newpos, ctrl[1], &estream) != 0) {
-            printf("error while reading extra stream\n");
-            return 1;
-        }
-
-        // Adjust pointers
-        newpos += ctrl[1];
-        oldpos += ctrl[2];
-    }
-
-    BZ2_bzDecompressEnd(&cstream);
-    BZ2_bzDecompressEnd(&dstream);
-    BZ2_bzDecompressEnd(&estream);
-    return 0;
+int ApplyBSDiffPatchMem(const unsigned char* old_data, ssize_t old_size, const Value* patch,
+                        ssize_t patch_offset, std::vector<unsigned char>* new_data) {
+  auto vector_sink = [new_data](const uint8_t* data, size_t len) {
+    new_data->insert(new_data->end(), data, data + len);
+    return len;
+  };
+  return bsdiff::bspatch(old_data, old_size,
+                         reinterpret_cast<const uint8_t*>(&patch->data[patch_offset]),
+                         patch->data.size(), vector_sink);
 }
diff --git a/applypatch/imgpatch.cpp b/applypatch/imgpatch.cpp
index 00ea90e..8f4a2a4 100644
--- a/applypatch/imgpatch.cpp
+++ b/applypatch/imgpatch.cpp
@@ -193,6 +193,9 @@
 
       // Next, apply the bsdiff patch (in memory) to the uncompressed data.
       std::vector<unsigned char> uncompressed_target_data;
+      // TODO(senj): Remove the only usage of ApplyBSDiffPatchMem here,
+      // replace it with ApplyBSDiffPatch with a custom sink function that
+      // wraps the given sink function to stream output to save memory.
       if (ApplyBSDiffPatchMem(expanded_source.data(), expanded_len, patch, patch_offset,
                               &uncompressed_target_data) != 0) {
         return -1;