Merge "Add Kobo's USB vendor ID to adb"
diff --git a/fastboot/Android.mk b/fastboot/Android.mk
index 089b9bb..e3261a7 100644
--- a/fastboot/Android.mk
+++ b/fastboot/Android.mk
@@ -48,7 +48,7 @@
LOCAL_C_INCLUDES += development/host/windows/usb/api
endif
-LOCAL_STATIC_LIBRARIES := $(EXTRA_STATIC_LIBS) libzipfile libunz libext4_utils libz
+LOCAL_STATIC_LIBRARIES := $(EXTRA_STATIC_LIBS) libzipfile libunz libext4_utils libsparse libz
ifneq ($(HOST_OS),windows)
ifeq ($(HAVE_SELINUX), true)
diff --git a/fastboot/engine.c b/fastboot/engine.c
index f5215cf..8d7b68a 100644
--- a/fastboot/engine.c
+++ b/fastboot/engine.c
@@ -28,7 +28,6 @@
#include "fastboot.h"
#include "make_ext4fs.h"
-#include "ext4_utils.h"
#include <stdio.h>
#include <stdlib.h>
@@ -77,6 +76,7 @@
#define OP_QUERY 3
#define OP_NOTICE 4
#define OP_FORMAT 5
+#define OP_DOWNLOAD_SPARSE 6
typedef struct Action Action;
@@ -111,6 +111,20 @@
void generate_ext4_image(struct image_data *image);
void cleanup_image(struct image_data *image);
+int fb_getvar(struct usb_handle *usb, char *response, const char *fmt, ...)
+{
+ char cmd[CMD_SIZE] = "getvar:";
+ int getvar_len = strlen(cmd);
+ va_list args;
+
+ response[FB_RESPONSE_SZ] = '\0';
+ va_start(args, fmt);
+ vsnprintf(cmd + getvar_len, sizeof(cmd) - getvar_len, fmt, args);
+ va_end(args);
+ cmd[CMD_SIZE - 1] = '\0';
+ return fb_command_response(usb, cmd, response);
+}
+
struct generator {
char *fs_type;
@@ -278,9 +292,7 @@
unsigned i;
char cmd[CMD_SIZE];
- response[FB_RESPONSE_SZ] = '\0';
- snprintf(cmd, sizeof(cmd), "getvar:partition-type:%s", partition);
- status = fb_command_response(usb, cmd, response);
+ status = fb_getvar(usb, response, "partition-type:%s", partition);
if (status) {
if (skip_if_not_supported) {
fprintf(stderr,
@@ -312,9 +324,7 @@
return -1;
}
- response[FB_RESPONSE_SZ] = '\0';
- snprintf(cmd, sizeof(cmd), "getvar:partition-size:%s", partition);
- status = fb_command_response(usb, cmd, response);
+ status = fb_getvar(usb, response, "partition-size:%s", partition);
if (status) {
if (skip_if_not_supported) {
fprintf(stderr,
@@ -372,6 +382,19 @@
a->msg = mkmsg("writing '%s'", ptn);
}
+void fb_queue_flash_sparse(const char *ptn, struct sparse_file *s, unsigned sz)
+{
+ Action *a;
+
+ a = queue_action(OP_DOWNLOAD_SPARSE, "");
+ a->data = s;
+ a->size = 0;
+ a->msg = mkmsg("sending sparse '%s' (%d KB)", ptn, sz / 1024);
+
+ a = queue_action(OP_COMMAND, "flash:%s", ptn);
+ a->msg = mkmsg("writing '%s'", ptn);
+}
+
static int match(char *str, const char **value, unsigned count)
{
const char *val;
@@ -572,6 +595,10 @@
status = fb_format(a, usb, (int)a->data);
status = a->func(a, status, status ? fb_get_error() : "");
if (status) break;
+ } else if (a->op == OP_DOWNLOAD_SPARSE) {
+ status = fb_download_data_sparse(usb, a->data);
+ status = a->func(a, status, status ? fb_get_error() : "");
+ if (status) break;
} else {
die("bogus action");
}
diff --git a/fastboot/fastboot.c b/fastboot/fastboot.c
index 544893b..6a14301 100644
--- a/fastboot/fastboot.c
+++ b/fastboot/fastboot.c
@@ -26,22 +26,36 @@
* SUCH DAMAGE.
*/
+#define _LARGEFILE64_SOURCE
+
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
+#include <stdbool.h>
+#include <stdint.h>
#include <string.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <limits.h>
#include <ctype.h>
+#include <getopt.h>
#include <sys/time.h>
+#include <sys/types.h>
+
#include <bootimg.h>
+#include <sparse/sparse.h>
#include <zipfile/zipfile.h>
#include "fastboot.h"
+#ifndef O_BINARY
+#define O_BINARY 0
+#endif
+
+#define DEFAULT_SPARSE_LIMIT (256 * 1024 * 1024)
+
char cur_product[FB_RESPONSE_SZ + 1];
void bootimg_set_cmdline(boot_img_hdr *h, const char *cmdline);
@@ -59,6 +73,8 @@
static int wipe_data = 0;
static unsigned short vendor_id = 0;
static int long_listing = 0;
+static int64_t sparse_limit = -1;
+static int64_t target_sparse_limit = -1;
static unsigned base_addr = 0x10000000;
@@ -117,7 +133,27 @@
#ifdef _WIN32
void *load_file(const char *fn, unsigned *_sz);
+int64_t file_size(const char *fn);
#else
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+int64_t file_size(const char *fn)
+{
+ off64_t off;
+ int fd;
+
+ fd = open(fn, O_RDONLY);
+ if (fd < 0) return -1;
+
+ off = lseek64(fd, 0, SEEK_END);
+ close(fd);
+
+ return off;
+}
+
void *load_file(const char *fn, unsigned *_sz)
{
char *data;
@@ -259,6 +295,8 @@
" -i <vendor id> specify a custom USB vendor id\n"
" -b <base_addr> specify a custom kernel base address\n"
" -n <page size> specify the nand page size. default: 2048\n"
+ " -S <size>[K|M|G] automatically sparse files greater than\n"
+ " size. default: 256M, 0 to disable\n"
);
}
@@ -444,6 +482,110 @@
fb_queue_notice("--------------------------------------------");
}
+
+struct sparse_file **load_sparse_files(const char *fname, int max_size)
+{
+ int fd;
+ struct sparse_file *s;
+ int files;
+ struct sparse_file **out_s;
+
+ fd = open(fname, O_RDONLY | O_BINARY);
+ if (fd < 0) {
+ die("cannot open '%s'\n", fname);
+ }
+
+ s = sparse_file_import_auto(fd, false);
+ if (!s) {
+ die("cannot sparse read file '%s'\n", fname);
+ }
+
+ files = sparse_file_resparse(s, max_size, NULL, 0);
+ if (files < 0) {
+ die("Failed to resparse '%s'\n", fname);
+ }
+
+ out_s = calloc(sizeof(struct sparse_file *), files + 1);
+ if (!out_s) {
+ die("Failed to allocate sparse file array\n");
+ }
+
+ files = sparse_file_resparse(s, max_size, out_s, files);
+ if (files < 0) {
+ die("Failed to resparse '%s'\n", fname);
+ }
+
+ return out_s;
+}
+
+static int64_t get_target_sparse_limit(struct usb_handle *usb)
+{
+ int64_t limit = 0;
+ char response[FB_RESPONSE_SZ + 1];
+ int status = fb_getvar(usb, response, "max-download-size");
+
+ if (!status) {
+ limit = strtoul(response, NULL, 0);
+ if (limit > 0) {
+ fprintf(stderr, "target reported max download size of %lld bytes\n",
+ limit);
+ }
+ }
+
+ return limit;
+}
+
+static int64_t get_sparse_limit(struct usb_handle *usb, int64_t size)
+{
+ int64_t limit;
+
+ if (sparse_limit == 0) {
+ return 0;
+ } else if (sparse_limit > 0) {
+ limit = sparse_limit;
+ } else {
+ if (target_sparse_limit == -1) {
+ target_sparse_limit = get_target_sparse_limit(usb);
+ }
+ if (target_sparse_limit > 0) {
+ limit = target_sparse_limit;
+ } else {
+ limit = DEFAULT_SPARSE_LIMIT;
+ }
+ }
+
+ if (size > limit) {
+ return limit;
+ }
+
+ return 0;
+}
+
+void do_flash(usb_handle *usb, const char *pname, const char *fname)
+{
+ int64_t sz64;
+ void *data;
+ int64_t limit;
+
+ sz64 = file_size(fname);
+ limit = get_sparse_limit(usb, sz64);
+ if (limit) {
+ struct sparse_file **s = load_sparse_files(fname, limit);
+ if (s == NULL) {
+ die("cannot sparse load '%s'\n", fname);
+ }
+ while (*s) {
+ sz64 = sparse_file_len(*s, true, false);
+ fb_queue_flash_sparse(pname, *s++, sz64);
+ }
+ } else {
+ unsigned int sz;
+ data = load_file(fname, &sz);
+ if (data == 0) die("cannot load '%s'\n", fname);
+ fb_queue_flash(pname, data, sz);
+ }
+}
+
void do_update_signature(zipfile_t zip, char *fn)
{
void *data;
@@ -581,73 +723,136 @@
return 0;
}
+static int64_t parse_num(const char *arg)
+{
+ char *endptr;
+ unsigned long long num;
+
+ num = strtoull(arg, &endptr, 0);
+ if (endptr == arg) {
+ return -1;
+ }
+
+ if (*endptr == 'k' || *endptr == 'K') {
+ if (num >= (-1ULL) / 1024) {
+ return -1;
+ }
+ num *= 1024LL;
+ endptr++;
+ } else if (*endptr == 'm' || *endptr == 'M') {
+ if (num >= (-1ULL) / (1024 * 1024)) {
+ return -1;
+ }
+ num *= 1024LL * 1024LL;
+ endptr++;
+ } else if (*endptr == 'g' || *endptr == 'G') {
+ if (num >= (-1ULL) / (1024 * 1024 * 1024)) {
+ return -1;
+ }
+ num *= 1024LL * 1024LL * 1024LL;
+ endptr++;
+ }
+
+ if (*endptr != '\0') {
+ return -1;
+ }
+
+ if (num > INT64_MAX) {
+ return -1;
+ }
+
+ return num;
+}
+
int main(int argc, char **argv)
{
int wants_wipe = 0;
int wants_reboot = 0;
int wants_reboot_bootloader = 0;
- int wants_device_list = 0;
void *data;
unsigned sz;
unsigned page_size = 2048;
int status;
+ int c;
+ int r;
- skip(1);
- if (argc == 0) {
+ const struct option longopts = { 0, 0, 0, 0 };
+
+ serial = getenv("ANDROID_SERIAL");
+
+ while (1) {
+ c = getopt_long(argc, argv, "wb:n:s:S:lp:c:i:m:h", &longopts, NULL);
+ if (c < 0) {
+ break;
+ }
+
+ switch (c) {
+ case 'w':
+ wants_wipe = 1;
+ break;
+ case 'b':
+ base_addr = strtoul(optarg, 0, 16);
+ break;
+ case 'n':
+ page_size = (unsigned)strtoul(optarg, NULL, 0);
+ if (!page_size) die("invalid page size");
+ break;
+ case 's':
+ serial = optarg;
+ break;
+ case 'S':
+ sparse_limit = parse_num(optarg);
+ if (sparse_limit < 0) {
+ die("invalid sparse limit");
+ }
+ break;
+ case 'l':
+ long_listing = 1;
+ break;
+ case 'p':
+ product = optarg;
+ break;
+ case 'c':
+ cmdline = optarg;
+ break;
+ case 'i': {
+ char *endptr = NULL;
+ unsigned long val;
+
+ val = strtoul(optarg, &endptr, 0);
+ if (!endptr || *endptr != '\0' || (val & ~0xffff))
+ die("invalid vendor id '%s'", optarg);
+ vendor_id = (unsigned short)val;
+ break;
+ }
+ case 'h':
+ usage();
+ return 1;
+ case '?':
+ return 1;
+ default:
+ abort();
+ }
+ }
+
+ argc -= optind;
+ argv += optind;
+
+ if (argc == 0 && !wants_wipe) {
usage();
return 1;
}
- if (!strcmp(*argv, "help")) {
- usage();
+ if (!strcmp(*argv, "devices")) {
+ skip(1);
+ list_devices();
return 0;
}
-
- serial = getenv("ANDROID_SERIAL");
+ usb = open_device();
while (argc > 0) {
- if(!strcmp(*argv, "-w")) {
- wants_wipe = 1;
- skip(1);
- } else if(!strcmp(*argv, "-b")) {
- require(2);
- base_addr = strtoul(argv[1], 0, 16);
- skip(2);
- } else if(!strcmp(*argv, "-n")) {
- require(2);
- page_size = (unsigned)strtoul(argv[1], NULL, 0);
- if (!page_size) die("invalid page size");
- skip(2);
- } else if(!strcmp(*argv, "-s")) {
- require(2);
- serial = argv[1];
- skip(2);
- } else if(!strcmp(*argv, "-l")) {
- long_listing = 1;
- skip(1);
- } else if(!strcmp(*argv, "-p")) {
- require(2);
- product = argv[1];
- skip(2);
- } else if(!strcmp(*argv, "-c")) {
- require(2);
- cmdline = argv[1];
- skip(2);
- } else if(!strcmp(*argv, "-i")) {
- char *endptr = NULL;
- unsigned long val;
-
- require(2);
- val = strtoul(argv[1], &endptr, 0);
- if (!endptr || *endptr != '\0' || (val & ~0xffff))
- die("invalid vendor id '%s'", argv[1]);
- vendor_id = (unsigned short)val;
- skip(2);
- } else if (!strcmp(*argv, "devices")) {
- skip(1);
- wants_device_list = 1;
- } else if(!strcmp(*argv, "getvar")) {
+ if(!strcmp(*argv, "getvar")) {
require(2);
fb_queue_display(argv[1], argv[1]);
skip(2);
@@ -704,9 +909,7 @@
skip(2);
}
if (fname == 0) die("cannot determine image filename for '%s'", pname);
- data = load_file(fname, &sz);
- if (data == 0) die("cannot load '%s'\n", fname);
- fb_queue_flash(pname, data, sz);
+ do_flash(usb, pname, fname);
} else if(!strcmp(*argv, "flash:raw")) {
char *pname = argv[1];
char *kname = argv[2];
@@ -736,15 +939,15 @@
wants_reboot = 1;
} else if(!strcmp(*argv, "oem")) {
argc = do_oem_command(argc, argv);
+ } else if (!strcmp(*argv, "help")) {
+ usage();
+ return 0;
} else {
usage();
return 1;
}
}
- if (wants_device_list)
- list_devices();
-
if (wants_wipe) {
fb_queue_erase("userdata");
fb_queue_format("userdata", 1);
@@ -760,8 +963,6 @@
if (fb_queue_is_empty())
return 0;
- usb = open_device();
-
status = fb_execute_queue(usb);
return (status) ? 1 : 0;
}
diff --git a/fastboot/fastboot.h b/fastboot/fastboot.h
index 90d8a6a..b4cf195 100644
--- a/fastboot/fastboot.h
+++ b/fastboot/fastboot.h
@@ -31,17 +31,22 @@
#include "usb.h"
+struct sparse_file;
+
/* protocol.c - fastboot protocol */
int fb_command(usb_handle *usb, const char *cmd);
int fb_command_response(usb_handle *usb, const char *cmd, char *response);
int fb_download_data(usb_handle *usb, const void *data, unsigned size);
+int fb_download_data_sparse(usb_handle *usb, struct sparse_file *s);
char *fb_get_error(void);
#define FB_COMMAND_SZ 64
#define FB_RESPONSE_SZ 64
/* engine.c - high level command queue engine */
+int fb_getvar(struct usb_handle *usb, char *response, const char *fmt, ...);
void fb_queue_flash(const char *ptn, void *data, unsigned sz);;
+void fb_queue_flash_sparse(const char *ptn, struct sparse_file *s, unsigned sz);
void fb_queue_erase(const char *ptn);
void fb_queue_format(const char *ptn, int skip_if_not_supported);
void fb_queue_require(const char *prod, const char *var, int invert,
diff --git a/fastboot/protocol.c b/fastboot/protocol.c
index e871113..a0e0fd4 100644
--- a/fastboot/protocol.c
+++ b/fastboot/protocol.c
@@ -26,11 +26,18 @@
* SUCH DAMAGE.
*/
+#define min(a, b) \
+ ({ typeof(a) _a = (a); typeof(b) _b = (b); (_a < _b) ? _a : _b; })
+#define round_down(a, b) \
+ ({ typeof(a) _a = (a); typeof(b) _b = (b); _a - (_a % _b); })
+
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
+#include <sparse/sparse.h>
+
#include "fastboot.h"
static char ERROR[128];
@@ -40,8 +47,7 @@
return ERROR;
}
-static int check_response(usb_handle *usb, unsigned size,
- unsigned data_okay, char *response)
+static int check_response(usb_handle *usb, unsigned int size, char *response)
{
unsigned char status[65];
int r;
@@ -82,7 +88,7 @@
return -1;
}
- if(!memcmp(status, "DATA", 4) && data_okay){
+ if(!memcmp(status, "DATA", 4) && size > 0){
unsigned dsize = strtoul((char*) status + 4, 0, 16);
if(dsize > size) {
strcpy(ERROR, "data size too large");
@@ -100,9 +106,8 @@
return -1;
}
-static int _command_send(usb_handle *usb, const char *cmd,
- const void *data, unsigned size,
- char *response)
+static int _command_start(usb_handle *usb, const char *cmd, unsigned size,
+ char *response)
{
int cmdsize = strlen(cmd);
int r;
@@ -122,46 +127,81 @@
return -1;
}
- if(data == 0) {
- return check_response(usb, size, 0, response);
+ return check_response(usb, size, response);
+}
+
+static int _command_data(usb_handle *usb, const void *data, unsigned size)
+{
+ int r;
+
+ r = usb_write(usb, data, size);
+ if(r < 0) {
+ sprintf(ERROR, "data transfer failure (%s)", strerror(errno));
+ usb_close(usb);
+ return -1;
+ }
+ if(r != ((int) size)) {
+ sprintf(ERROR, "data transfer failure (short transfer)");
+ usb_close(usb);
+ return -1;
}
- r = check_response(usb, size, 1, 0);
+ return r;
+}
+
+static int _command_end(usb_handle *usb)
+{
+ int r;
+ r = check_response(usb, 0, 0);
if(r < 0) {
return -1;
}
- size = r;
+ return 0;
+}
- if(size) {
- r = usb_write(usb, data, size);
- if(r < 0) {
- sprintf(ERROR, "data transfer failure (%s)", strerror(errno));
- usb_close(usb);
- return -1;
- }
- if(r != ((int) size)) {
- sprintf(ERROR, "data transfer failure (short transfer)");
- usb_close(usb);
- return -1;
- }
+static int _command_send(usb_handle *usb, const char *cmd,
+ const void *data, unsigned size,
+ char *response)
+{
+ int r;
+ if (size == 0) {
+ return -1;
}
- r = check_response(usb, 0, 0, 0);
+ r = _command_start(usb, cmd, size, response);
+ if (r < 0) {
+ return -1;
+ }
+
+ r = _command_data(usb, data, size);
+ if (r < 0) {
+ return -1;
+ }
+
+ r = _command_end(usb);
if(r < 0) {
return -1;
- } else {
- return size;
}
+
+ return size;
+}
+
+static int _command_send_no_data(usb_handle *usb, const char *cmd,
+ char *response)
+{
+ int r;
+
+ return _command_start(usb, cmd, 0, response);
}
int fb_command(usb_handle *usb, const char *cmd)
{
- return _command_send(usb, cmd, 0, 0, 0);
+ return _command_send_no_data(usb, cmd, 0);
}
int fb_command_response(usb_handle *usb, const char *cmd, char *response)
{
- return _command_send(usb, cmd, 0, 0, response);
+ return _command_send_no_data(usb, cmd, response);
}
int fb_download_data(usb_handle *usb, const void *data, unsigned size)
@@ -179,3 +219,96 @@
}
}
+#define USB_BUF_SIZE 512
+static char usb_buf[USB_BUF_SIZE];
+static int usb_buf_len;
+
+static int fb_download_data_sparse_write(void *priv, const void *data, int len)
+{
+ int r;
+ usb_handle *usb = priv;
+ int to_write;
+ const char *ptr = data;
+
+ if (usb_buf_len) {
+ to_write = min(USB_BUF_SIZE - usb_buf_len, len);
+
+ memcpy(usb_buf + usb_buf_len, ptr, to_write);
+ usb_buf_len += to_write;
+ ptr += to_write;
+ len -= to_write;
+ }
+
+ if (usb_buf_len == USB_BUF_SIZE) {
+ r = _command_data(usb, usb_buf, USB_BUF_SIZE);
+ if (r != USB_BUF_SIZE) {
+ return -1;
+ }
+ usb_buf_len = 0;
+ }
+
+ if (len > USB_BUF_SIZE) {
+ if (usb_buf_len > 0) {
+ sprintf(ERROR, "internal error: usb_buf not empty\n");
+ return -1;
+ }
+ to_write = round_down(len, USB_BUF_SIZE);
+ r = _command_data(usb, ptr, to_write);
+ if (r != to_write) {
+ return -1;
+ }
+ ptr += to_write;
+ len -= to_write;
+ }
+
+ if (len > 0) {
+ if (len > USB_BUF_SIZE) {
+ sprintf(ERROR, "internal error: too much left for usb_buf\n");
+ return -1;
+ }
+ memcpy(usb_buf, ptr, len);
+ usb_buf_len = len;
+ }
+
+ return 0;
+}
+
+static int fb_download_data_sparse_flush(usb_handle *usb)
+{
+ int r;
+
+ if (usb_buf_len > 0) {
+ r = _command_data(usb, usb_buf, usb_buf_len);
+ if (r != usb_buf_len) {
+ return -1;
+ }
+ usb_buf_len = 0;
+ }
+
+ return 0;
+}
+
+int fb_download_data_sparse(usb_handle *usb, struct sparse_file *s)
+{
+ char cmd[64];
+ int r;
+ int size = sparse_file_len(s, true, false);
+ if (size <= 0) {
+ return -1;
+ }
+
+ sprintf(cmd, "download:%08x", size);
+ r = _command_start(usb, cmd, size, 0);
+ if (r < 0) {
+ return -1;
+ }
+
+ r = sparse_file_callback(s, true, false, fb_download_data_sparse_write, usb);
+ if (r < 0) {
+ return -1;
+ }
+
+ fb_download_data_sparse_flush(usb);
+
+ return _command_end(usb);
+}
diff --git a/fastboot/util_windows.c b/fastboot/util_windows.c
index c3d545c..9e029fd 100644
--- a/fastboot/util_windows.c
+++ b/fastboot/util_windows.c
@@ -36,6 +36,29 @@
#include <windows.h>
+int64_t file_size(const char *fn)
+{
+ HANDLE file;
+ char *data;
+ DWORD sz;
+
+ file = CreateFile( fn,
+ GENERIC_READ,
+ FILE_SHARE_READ,
+ NULL,
+ OPEN_EXISTING,
+ 0,
+ NULL );
+
+ if (file == INVALID_HANDLE_VALUE)
+ return -1;
+
+ sz = GetFileSize( file, NULL );
+ CloseHandle( file );
+
+ return sz;
+}
+
void get_my_path(char exe[PATH_MAX])
{
char* r;
@@ -52,7 +75,7 @@
{
HANDLE file;
char *data;
- DWORD file_size;
+ DWORD sz;
file = CreateFile( fn,
GENERIC_READ,
@@ -65,29 +88,29 @@
if (file == INVALID_HANDLE_VALUE)
return NULL;
- file_size = GetFileSize( file, NULL );
+ sz = GetFileSize( file, NULL );
data = NULL;
- if (file_size > 0) {
- data = (char*) malloc( file_size );
+ if (sz > 0) {
+ data = (char*) malloc( sz );
if (data == NULL) {
- fprintf(stderr, "load_file: could not allocate %ld bytes\n", file_size );
- file_size = 0;
+ fprintf(stderr, "load_file: could not allocate %ld bytes\n", sz );
+ sz = 0;
} else {
DWORD out_bytes;
- if ( !ReadFile( file, data, file_size, &out_bytes, NULL ) ||
- out_bytes != file_size )
+ if ( !ReadFile( file, data, sz, &out_bytes, NULL ) ||
+ out_bytes != sz )
{
- fprintf(stderr, "load_file: could not read %ld bytes from '%s'\n", file_size, fn);
+ fprintf(stderr, "load_file: could not read %ld bytes from '%s'\n", sz, fn);
free(data);
data = NULL;
- file_size = 0;
+ sz = 0;
}
}
}
CloseHandle( file );
- *_sz = (unsigned) file_size;
+ *_sz = (unsigned) sz;
return data;
}
diff --git a/libnl_2/genl/genl.c b/libnl_2/genl/genl.c
index 2442993..05431d6 100644
--- a/libnl_2/genl/genl.c
+++ b/libnl_2/genl/genl.c
@@ -21,6 +21,8 @@
#include <stdio.h>
#include <sys/time.h>
#include <linux/netlink.h>
+#include <netlink/genl/ctrl.h>
+#include <netlink/genl/family.h>
#include "netlink-types.h"
/* Get head of attribute data. */
@@ -250,7 +252,6 @@
struct genl_family *genl_ctrl_search_by_name(struct nl_cache *cache, \
const char *name)
{
- /* TODO: When will we release this memory ? */
struct genl_family *gf = (struct genl_family *) \
malloc(sizeof(struct genl_family));
if (!gf)
@@ -262,7 +263,7 @@
/* Overriding cache pointer as family id for now */
gf->gf_id = (uint16_t) ((uint32_t) cache);
- strcpy(gf->gf_name, "nl80211");
+ strncpy(gf->gf_name, name, GENL_NAMSIZ);
return gf;
fail:
@@ -272,15 +273,29 @@
int genl_ctrl_resolve(struct nl_sock *sk, const char *name)
{
+ struct nl_cache *cache = NULL;
+ struct genl_family *gf = NULL;
+ int id = -1;
+
/* Hack to support wpa_supplicant */
if (strcmp(name, "nlctrl") == 0)
return NETLINK_GENERIC;
- else {
- int errsv = errno;
- fprintf(stderr, \
- "Only nlctrl supported by genl_ctrl_resolve!\n");
- return -errsv;
+
+ if (strcmp(name, "nl80211") != 0) {
+ fprintf(stderr, "%s is not supported\n", name);
+ return id;
}
-}
+ if (!genl_ctrl_alloc_cache(sk, &cache)) {
+ gf = genl_ctrl_search_by_name(cache, name);
+ if (gf)
+ id = genl_family_get_id(gf);
+ }
+ if (gf)
+ genl_family_put(gf);
+ if (cache)
+ nl_cache_free(cache);
+
+ return id;
+}
diff --git a/libnl_2/socket.c b/libnl_2/socket.c
index d906cac..e94eb9e 100644
--- a/libnl_2/socket.c
+++ b/libnl_2/socket.c
@@ -127,3 +127,15 @@
{
return sk->s_fd;
}
+
+void nl_socket_set_cb(struct nl_sock *sk, struct nl_cb *cb)
+{
+ nl_cb_put(sk->s_cb);
+ sk->s_cb = cb;
+ nl_cb_get(cb);
+}
+
+struct nl_cb *nl_socket_get_cb(struct nl_sock *sk)
+{
+ return nl_cb_get(sk->s_cb);
+}
diff --git a/libsparse/Android.mk b/libsparse/Android.mk
new file mode 100644
index 0000000..69b52c3
--- /dev/null
+++ b/libsparse/Android.mk
@@ -0,0 +1,101 @@
+# Copyright 2010 The Android Open Source Project
+
+LOCAL_PATH:= $(call my-dir)
+
+libsparse_src_files := \
+ backed_block.c \
+ output_file.c \
+ sparse.c \
+ sparse_crc32.c \
+ sparse_err.c \
+ sparse_read.c
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_STATIC_LIBRARIES := libz
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+
+include $(BUILD_HOST_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+LOCAL_SHARED_LIBRARIES := libz
+
+include $(BUILD_SHARED_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include
+LOCAL_SRC_FILES := $(libsparse_src_files)
+LOCAL_MODULE := libsparse
+LOCAL_MODULE_TAGS := optional
+LOCAL_C_INCLUDES += $(LOCAL_PATH)/include external/zlib
+LOCAL_STATIC_LIBRARIES := libz
+
+include $(BUILD_STATIC_LIBRARY)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2img.c \
+ sparse_crc32.c
+LOCAL_MODULE := simg2img
+LOCAL_MODULE_TAGS := debug
+LOCAL_STATIC_LIBRARIES := libsparse libz
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2img.c \
+ sparse_crc32.c
+LOCAL_MODULE := simg2img
+LOCAL_MODULE_TAGS := optional
+LOCAL_STATIC_LIBRARIES := libsparse libz
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := img2simg.c
+LOCAL_MODULE := img2simg
+LOCAL_MODULE_TAGS := debug
+LOCAL_STATIC_LIBRARIES := libsparse libz
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := img2simg.c
+LOCAL_MODULE := img2simg
+LOCAL_MODULE_TAGS := optional
+LOCAL_STATIC_LIBRARIES := libsparse libz
+
+include $(BUILD_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_SRC_FILES := simg2simg.c
+LOCAL_MODULE := simg2simg
+LOCAL_MODULE_TAGS := debug
+LOCAL_STATIC_LIBRARIES := libsparse libz
+
+include $(BUILD_HOST_EXECUTABLE)
+
+include $(CLEAR_VARS)
+
+LOCAL_MODULE := simg_dump.py
+LOCAL_MODULE_TAGS := debug
+LOCAL_SRC_FILES := simg_dump.py
+LOCAL_MODULE_CLASS := EXECUTABLES
+LOCAL_IS_HOST_MODULE := true
+
+include $(BUILD_PREBUILT)
diff --git a/libsparse/backed_block.c b/libsparse/backed_block.c
new file mode 100644
index 0000000..dfb217b
--- /dev/null
+++ b/libsparse/backed_block.c
@@ -0,0 +1,400 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <assert.h>
+#include <errno.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "backed_block.h"
+#include "sparse_defs.h"
+
+struct backed_block {
+ unsigned int block;
+ unsigned int len;
+ enum backed_block_type type;
+ union {
+ struct {
+ void *data;
+ } data;
+ struct {
+ char *filename;
+ int64_t offset;
+ } file;
+ struct {
+ int fd;
+ int64_t offset;
+ } fd;
+ struct {
+ uint32_t val;
+ } fill;
+ };
+ struct backed_block *next;
+};
+
+struct backed_block_list {
+ struct backed_block *data_blocks;
+ struct backed_block *last_used;
+ unsigned int block_size;
+};
+
+struct backed_block *backed_block_iter_new(struct backed_block_list *bbl)
+{
+ return bbl->data_blocks;
+}
+
+struct backed_block *backed_block_iter_next(struct backed_block *bb)
+{
+ return bb->next;
+}
+
+unsigned int backed_block_len(struct backed_block *bb)
+{
+ return bb->len;
+}
+
+unsigned int backed_block_block(struct backed_block *bb)
+{
+ return bb->block;
+}
+
+void *backed_block_data(struct backed_block *bb)
+{
+ assert(bb->type == BACKED_BLOCK_DATA);
+ return bb->data.data;
+}
+
+const char *backed_block_filename(struct backed_block *bb)
+{
+ assert(bb->type == BACKED_BLOCK_FILE);
+ return bb->file.filename;
+}
+
+int backed_block_fd(struct backed_block *bb)
+{
+ assert(bb->type == BACKED_BLOCK_FD);
+ return bb->fd.fd;
+}
+
+int64_t backed_block_file_offset(struct backed_block *bb)
+{
+ assert(bb->type == BACKED_BLOCK_FILE || bb->type == BACKED_BLOCK_FD);
+ if (bb->type == BACKED_BLOCK_FILE) {
+ return bb->file.offset;
+ } else { /* bb->type == BACKED_BLOCK_FD */
+ return bb->fd.offset;
+ }
+}
+
+uint32_t backed_block_fill_val(struct backed_block *bb)
+{
+ assert(bb->type == BACKED_BLOCK_FILL);
+ return bb->fill.val;
+}
+
+enum backed_block_type backed_block_type(struct backed_block *bb)
+{
+ return bb->type;
+}
+
+void backed_block_destroy(struct backed_block *bb)
+{
+ if (bb->type == BACKED_BLOCK_FILE) {
+ free(bb->file.filename);
+ }
+
+ free(bb);
+}
+
+struct backed_block_list *backed_block_list_new(unsigned int block_size)
+{
+ struct backed_block_list *b = calloc(sizeof(struct backed_block_list), 1);
+ b->block_size = block_size;
+ return b;
+}
+
+void backed_block_list_destroy(struct backed_block_list *bbl)
+{
+ if (bbl->data_blocks) {
+ struct backed_block *bb = bbl->data_blocks;
+ while (bb) {
+ struct backed_block *next = bb->next;
+ backed_block_destroy(bb);
+ bb = next;
+ }
+ }
+
+ free(bbl);
+}
+
+void backed_block_list_move(struct backed_block_list *from,
+ struct backed_block_list *to, struct backed_block *start,
+ struct backed_block *end)
+{
+ struct backed_block *bb;
+
+ if (start == NULL) {
+ start = from->data_blocks;
+ }
+
+ if (!end) {
+ for (end = start; end && end->next; end = end->next)
+ ;
+ }
+
+ if (start == NULL || end == NULL) {
+ return;
+ }
+
+ from->last_used = NULL;
+ to->last_used = NULL;
+ if (from->data_blocks == start) {
+ from->data_blocks = end->next;
+ } else {
+ for (bb = from->data_blocks; bb; bb = bb->next) {
+ if (bb->next == start) {
+ bb->next = end->next;
+ break;
+ }
+ }
+ }
+
+ if (!to->data_blocks) {
+ to->data_blocks = start;
+ end->next = NULL;
+ } else {
+ for (bb = to->data_blocks; bb; bb = bb->next) {
+ if (!bb->next || bb->next->block > start->block) {
+ end->next = bb->next;
+ bb->next = start;
+ break;
+ }
+ }
+ }
+}
+
+/* may free b */
+static int merge_bb(struct backed_block_list *bbl,
+ struct backed_block *a, struct backed_block *b)
+{
+ unsigned int block_len;
+
+ /* Block doesn't exist (possible if one block is the last block) */
+ if (!a || !b) {
+ return -EINVAL;
+ }
+
+ assert(a->block < b->block);
+
+ /* Blocks are of different types */
+ if (a->type != b->type) {
+ return -EINVAL;
+ }
+
+ /* Blocks are not adjacent */
+ block_len = a->len / bbl->block_size; /* rounds down */
+ if (a->block + block_len != b->block) {
+ return -EINVAL;
+ }
+
+ switch (a->type) {
+ case BACKED_BLOCK_DATA:
+ /* Don't support merging data for now */
+ return -EINVAL;
+ case BACKED_BLOCK_FILL:
+ if (a->fill.val != b->fill.val) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FILE:
+ if (a->file.filename != b->file.filename ||
+ a->file.offset + a->len != b->file.offset) {
+ return -EINVAL;
+ }
+ break;
+ case BACKED_BLOCK_FD:
+ if (a->fd.fd != b->fd.fd ||
+ a->fd.offset + a->len != b->fd.offset) {
+ return -EINVAL;
+ }
+ break;
+ }
+
+ /* Blocks are compatible and adjacent, with a before b. Merge b into a,
+ * and free b */
+ a->len += b->len;
+ a->next = b->next;
+
+ backed_block_destroy(b);
+
+ return 0;
+}
+
+static int queue_bb(struct backed_block_list *bbl, struct backed_block *new_bb)
+{
+ struct backed_block *bb;
+
+ if (bbl->data_blocks == NULL) {
+ bbl->data_blocks = new_bb;
+ return 0;
+ }
+
+ if (bbl->data_blocks->block > new_bb->block) {
+ new_bb->next = bbl->data_blocks;
+ bbl->data_blocks = new_bb;
+ return 0;
+ }
+
+ /* Optimization: blocks are mostly queued in sequence, so save the
+ pointer to the last bb that was added, and start searching from
+ there if the next block number is higher */
+ if (bbl->last_used && new_bb->block > bbl->last_used->block)
+ bb = bbl->last_used;
+ else
+ bb = bbl->data_blocks;
+ bbl->last_used = new_bb;
+
+ for (; bb->next && bb->next->block < new_bb->block; bb = bb->next)
+ ;
+
+ if (bb->next == NULL) {
+ bb->next = new_bb;
+ } else {
+ new_bb->next = bb->next;
+ bb->next = new_bb;
+ }
+
+ merge_bb(bbl, new_bb, new_bb->next);
+ merge_bb(bbl, bb, new_bb);
+
+ return 0;
+}
+
+/* Queues a fill block of memory to be written to the specified data blocks */
+int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
+ unsigned int len, unsigned int block)
+{
+ struct backed_block *bb = calloc(1, sizeof(struct backed_block));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FILL;
+ bb->fill.val = fill_val;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
+}
+
+/* Queues a block of memory to be written to the specified data blocks */
+int backed_block_add_data(struct backed_block_list *bbl, void *data,
+ unsigned int len, unsigned int block)
+{
+ struct backed_block *bb = calloc(1, sizeof(struct backed_block));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_DATA;
+ bb->data.data = data;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
+}
+
+/* Queues a chunk of a file on disk to be written to the specified data blocks */
+int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
+ int64_t offset, unsigned int len, unsigned int block)
+{
+ struct backed_block *bb = calloc(1, sizeof(struct backed_block));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FILE;
+ bb->file.filename = strdup(filename);
+ bb->file.offset = offset;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
+}
+
+/* Queues a chunk of a fd to be written to the specified data blocks */
+int backed_block_add_fd(struct backed_block_list *bbl, int fd, int64_t offset,
+ unsigned int len, unsigned int block)
+{
+ struct backed_block *bb = calloc(1, sizeof(struct backed_block));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ bb->block = block;
+ bb->len = len;
+ bb->type = BACKED_BLOCK_FD;
+ bb->fd.fd = fd;
+ bb->fd.offset = offset;
+ bb->next = NULL;
+
+ return queue_bb(bbl, bb);
+}
+
+int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
+ unsigned int max_len)
+{
+ struct backed_block *new_bb;
+
+ max_len = ALIGN_DOWN(max_len, bbl->block_size);
+
+ if (bb->len <= max_len) {
+ return 0;
+ }
+
+ new_bb = malloc(sizeof(struct backed_block));
+ if (bb == NULL) {
+ return -ENOMEM;
+ }
+
+ *new_bb = *bb;
+
+ new_bb->len = bb->len - max_len;
+ new_bb->block = bb->block + max_len / bbl->block_size;
+ new_bb->next = bb->next;
+ bb->next = new_bb;
+ bb->len = max_len;
+
+ switch (bb->type) {
+ case BACKED_BLOCK_DATA:
+ new_bb->data.data = (char *)bb->data.data + max_len;
+ break;
+ case BACKED_BLOCK_FILE:
+ new_bb->file.offset += max_len;
+ break;
+ case BACKED_BLOCK_FD:
+ new_bb->fd.offset += max_len;
+ break;
+ case BACKED_BLOCK_FILL:
+ break;
+ }
+
+ return 0;
+}
diff --git a/libsparse/backed_block.h b/libsparse/backed_block.h
new file mode 100644
index 0000000..1a159be
--- /dev/null
+++ b/libsparse/backed_block.h
@@ -0,0 +1,64 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _BACKED_BLOCK_H_
+#define _BACKED_BLOCK_H_
+
+#include <stdint.h>
+
+struct backed_block_list;
+struct backed_block;
+
+enum backed_block_type {
+ BACKED_BLOCK_DATA,
+ BACKED_BLOCK_FILE,
+ BACKED_BLOCK_FD,
+ BACKED_BLOCK_FILL,
+};
+
+int backed_block_add_data(struct backed_block_list *bbl, void *data,
+ unsigned int len, unsigned int block);
+int backed_block_add_fill(struct backed_block_list *bbl, unsigned int fill_val,
+ unsigned int len, unsigned int block);
+int backed_block_add_file(struct backed_block_list *bbl, const char *filename,
+ int64_t offset, unsigned int len, unsigned int block);
+int backed_block_add_fd(struct backed_block_list *bbl, int fd,
+ int64_t offset, unsigned int len, unsigned int block);
+
+struct backed_block *backed_block_iter_new(struct backed_block_list *bbl);
+struct backed_block *backed_block_iter_next(struct backed_block *bb);
+unsigned int backed_block_len(struct backed_block *bb);
+unsigned int backed_block_block(struct backed_block *bb);
+void *backed_block_data(struct backed_block *bb);
+const char *backed_block_filename(struct backed_block *bb);
+int backed_block_fd(struct backed_block *bb);
+int64_t backed_block_file_offset(struct backed_block *bb);
+uint32_t backed_block_fill_val(struct backed_block *bb);
+enum backed_block_type backed_block_type(struct backed_block *bb);
+int backed_block_split(struct backed_block_list *bbl, struct backed_block *bb,
+ unsigned int max_len);
+
+struct backed_block *backed_block_iter_new(struct backed_block_list *bbl);
+struct backed_block *backed_block_iter_next(struct backed_block *bb);
+
+struct backed_block_list *backed_block_list_new(unsigned int block_size);
+void backed_block_list_destroy(struct backed_block_list *bbl);
+
+void backed_block_list_move(struct backed_block_list *from,
+ struct backed_block_list *to, struct backed_block *start,
+ struct backed_block *end);
+
+#endif
diff --git a/libsparse/img2simg.c b/libsparse/img2simg.c
new file mode 100644
index 0000000..6b1caa5
--- /dev/null
+++ b/libsparse/img2simg.c
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <sparse/sparse.h>
+
+#ifndef O_BINARY
+#define O_BINARY 0
+#endif
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+void usage()
+{
+ fprintf(stderr, "Usage: img2simg <raw_image_file> <sparse_image_file> [<block_size>]\n");
+}
+
+int main(int argc, char *argv[])
+{
+ int in;
+ int out;
+ unsigned int i;
+ int ret;
+ struct sparse_file *s;
+ unsigned int block_size = 4096;
+ off64_t len;
+
+ if (argc < 3 || argc > 4) {
+ usage();
+ exit(-1);
+ }
+
+ if (argc == 4) {
+ block_size = atoi(argv[3]);
+ }
+
+ if (block_size < 1024 || block_size % 4 != 0) {
+ usage();
+ exit(-1);
+ }
+
+ if (strcmp(argv[1], "-") == 0) {
+ in = STDIN_FILENO;
+ } else {
+ in = open(argv[1], O_RDONLY | O_BINARY);
+ if (in < 0) {
+ fprintf(stderr, "Cannot open input file %s\n", argv[1]);
+ exit(-1);
+ }
+ }
+
+ if (strcmp(argv[2], "-") == 0) {
+ out = STDOUT_FILENO;
+ } else {
+ out = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0664);
+ if (out < 0) {
+ fprintf(stderr, "Cannot open output file %s\n", argv[2]);
+ exit(-1);
+ }
+ }
+
+ len = lseek64(in, 0, SEEK_END);
+ lseek64(in, 0, SEEK_SET);
+
+ s = sparse_file_new(block_size, len);
+ if (!s) {
+ fprintf(stderr, "Failed to create sparse file\n");
+ exit(-1);
+ }
+
+ sparse_file_verbose(s);
+ ret = sparse_file_read(s, in, false, false);
+ if (ret) {
+ fprintf(stderr, "Failed to read file\n");
+ exit(-1);
+ }
+
+ ret = sparse_file_write(s, out, false, true, false);
+ if (ret) {
+ fprintf(stderr, "Failed to write sparse file\n");
+ exit(-1);
+ }
+
+ close(in);
+ close(out);
+
+ exit(0);
+}
diff --git a/libsparse/include/sparse/sparse.h b/libsparse/include/sparse/sparse.h
new file mode 100644
index 0000000..17d085c
--- /dev/null
+++ b/libsparse/include/sparse/sparse.h
@@ -0,0 +1,276 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_H_
+#define _LIBSPARSE_SPARSE_H_
+
+#include <stdbool.h>
+#include <stdint.h>
+
+struct sparse_file;
+
+/**
+ * sparse_file_new - create a new sparse file cookie
+ *
+ * @block_size - minimum size of a chunk
+ * @len - size of the expanded sparse file.
+ *
+ * Creates a new sparse_file cookie that can be used to associate data
+ * blocks. Can later be written to a file with a variety of options.
+ * block_size specifies the minimum size of a chunk in the file. The maximum
+ * size of the file is 2**32 * block_size (16TB for 4k block size).
+ *
+ * Returns the sparse file cookie, or NULL on error.
+ */
+struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len);
+
+/**
+ * sparse_file_destroy - destroy a sparse file cookie
+ *
+ * @s - sparse file cookie
+ *
+ * Destroys a sparse file cookie. After destroy, all memory passed in to
+ * sparse_file_add_data can be freed by the caller
+ */
+void sparse_file_destroy(struct sparse_file *s);
+
+/**
+ * sparse_file_add_data - associate a data chunk with a sparse file
+ *
+ * @s - sparse file cookie
+ * @data - pointer to data block
+ * @len - length of the data block
+ * @block - offset in blocks into the sparse file to place the data chunk
+ *
+ * Associates a data chunk with a sparse file cookie. The region
+ * [block * block_size : block * block_size + len) must not already be used in
+ * the sparse file. If len is not a multiple of the block size the data
+ * will be padded with zeros.
+ *
+ * The data pointer must remain valid until the sparse file is closed or the
+ * data block is removed from the sparse file.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_data(struct sparse_file *s,
+ void *data, unsigned int len, unsigned int block);
+
+/**
+ * sparse_file_add_fill - associate a fill chunk with a sparse file
+ *
+ * @s - sparse file cookie
+ * @fill_val - 32 bit fill data
+ * @len - length of the fill block
+ * @block - offset in blocks into the sparse file to place the fill chunk
+ *
+ * Associates a chunk filled with fill_val with a sparse file cookie.
+ * The region [block * block_size : block * block_size + len) must not already
+ * be used in the sparse file. If len is not a multiple of the block size the
+ * data will be padded with zeros.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_fill(struct sparse_file *s,
+ uint32_t fill_val, unsigned int len, unsigned int block);
+
+/**
+ * sparse_file_add_file - associate a chunk of a file with a sparse file
+ *
+ * @s - sparse file cookie
+ * @filename - filename of the file to be copied
+ * @file_offset - offset into the copied file
+ * @len - length of the copied block
+ * @block - offset in blocks into the sparse file to place the file chunk
+ *
+ * Associates a chunk of an existing file with a sparse file cookie.
+ * The region [block * block_size : block * block_size + len) must not already
+ * be used in the sparse file. If len is not a multiple of the block size the
+ * data will be padded with zeros.
+ *
+ * Allows adding large amounts of data to a sparse file without needing to keep
+ * it all mapped. File size is limited by available virtual address space,
+ * exceptionally large files may need to be added in multiple chunks.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_file(struct sparse_file *s,
+ const char *filename, int64_t file_offset, unsigned int len,
+ unsigned int block);
+
+/**
+ * sparse_file_add_file - associate a chunk of a file with a sparse file
+ *
+ * @s - sparse file cookie
+ * @filename - filename of the file to be copied
+ * @file_offset - offset into the copied file
+ * @len - length of the copied block
+ * @block - offset in blocks into the sparse file to place the file chunk
+ *
+ * Associates a chunk of an existing fd with a sparse file cookie.
+ * The region [block * block_size : block * block_size + len) must not already
+ * be used in the sparse file. If len is not a multiple of the block size the
+ * data will be padded with zeros.
+ *
+ * Allows adding large amounts of data to a sparse file without needing to keep
+ * it all mapped. File size is limited by available virtual address space,
+ * exceptionally large files may need to be added in multiple chunks.
+ *
+ * The fd must remain open until the sparse file is closed or the fd block is
+ * removed from the sparse file.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_add_fd(struct sparse_file *s,
+ int fd, int64_t file_offset, unsigned int len, unsigned int block);
+
+/**
+ * sparse_file_write - write a sparse file to a file
+ *
+ * @s - sparse file cookie
+ * @fd - file descriptor to write to
+ * @gz - write a gzipped file
+ * @sparse - write in the Android sparse file format
+ * @crc - append a crc chunk
+ *
+ * Writes a sparse file to a file. If gz is true, the data will be passed
+ * through zlib. If sparse is true, the file will be written in the Android
+ * sparse file format. If sparse is false, the file will be written by seeking
+ * over unused chunks, producing a smaller file if the filesystem supports
+ * sparse files. If crc is true, the crc of the expanded data will be
+ * calculated and appended in a crc chunk.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
+ bool crc);
+
+/**
+ * sparse_file_len - return the length of a sparse file if written to disk
+ *
+ * @s - sparse file cookie
+ * @sparse - write in the Android sparse file format
+ * @crc - append a crc chunk
+ *
+ * Returns the size a sparse file would be on disk if it were written in the
+ * specified format. If sparse is true, this is the size of the data in the
+ * sparse format. If sparse is false, this is the size of the normal
+ * non-sparse file.
+ */
+int64_t sparse_file_len(struct sparse_file *s, bool sparse, bool crc);
+
+/**
+ * sparse_file_callback - call a callback for blocks in sparse file
+ *
+ * @s - sparse file cookie
+ * @sparse - write in the Android sparse file format
+ * @crc - append a crc chunk
+ * @write - function to call for each block
+ * @priv - value that will be passed as the first argument to write
+ *
+ * Writes a sparse file by calling a callback function. If sparse is true, the
+ * file will be written in the Android sparse file format. If crc is true, the
+ * crc of the expanded data will be calculated and appended in a crc chunk.
+ * The callback 'write' will be called with data and length for each data,
+ * and with data==NULL to skip over a region (only used for non-sparse format).
+ * The callback should return negative on error, 0 on success.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_callback(struct sparse_file *s, bool sparse, bool crc,
+ int (*write)(void *priv, const void *data, int len), void *priv);
+
+/**
+ * sparse_file_read - read a file into a sparse file cookie
+ *
+ * @s - sparse file cookie
+ * @fd - file descriptor to read from
+ * @sparse - read a file in the Android sparse file format
+ * @crc - verify the crc of a file in the Android sparse file format
+ *
+ * Reads a file into a sparse file cookie. If sparse is true, the file is
+ * assumed to be in the Android sparse file format. If sparse is false, the
+ * file will be sparsed by looking for block aligned chunks of all zeros or
+ * another 32 bit value. If crc is true, the crc of the sparse file will be
+ * verified.
+ *
+ * Returns 0 on success, negative errno on error.
+ */
+int sparse_file_read(struct sparse_file *s, int fd, bool sparse, bool crc);
+
+/**
+ * sparse_file_import - import an existing sparse file
+ *
+ * @s - sparse file cookie
+ * @verbose - print verbose errors while reading the sparse file
+ * @crc - verify the crc of a file in the Android sparse file format
+ *
+ * Reads an existing sparse file into a sparse file cookie, recreating the same
+ * sparse cookie that was used to write it. If verbose is true, prints verbose
+ * errors when the sparse file is formatted incorrectly.
+ *
+ * Returns a new sparse file cookie on success, NULL on error.
+ */
+struct sparse_file *sparse_file_import(int fd, bool verbose, bool crc);
+
+/**
+ * sparse_file_import_auto - import an existing sparse or normal file
+ *
+ * @fd - file descriptor to read from
+ * @crc - verify the crc of a file in the Android sparse file format
+ *
+ * Reads an existing sparse or normal file into a sparse file cookie.
+ * Attempts to determine if the file is sparse or not by looking for the sparse
+ * file magic number in the first 4 bytes. If the file is not sparse, the file
+ * will be sparsed by looking for block aligned chunks of all zeros or another
+ * 32 bit value. If crc is true, the crc of the sparse file will be verified.
+ *
+ * Returns a new sparse file cookie on success, NULL on error.
+ */
+struct sparse_file *sparse_file_import_auto(int fd, bool crc);
+
+/** sparse_file_resparse - rechunk an existing sparse file into smaller files
+ *
+ * @in_s - sparse file cookie of the existing sparse file
+ * @max_len - maximum file size
+ * @out_s - array of sparse file cookies
+ * @out_s_count - size of out_s array
+ *
+ * Splits chunks of an existing sparse file into smaller sparse files such that
+ * each sparse file is less than max_len. Returns the number of sparse_files
+ * that would have been written to out_s if out_s were big enough.
+ */
+int sparse_file_resparse(struct sparse_file *in_s, unsigned int max_len,
+ struct sparse_file **out_s, int out_s_count);
+
+/**
+ * sparse_file_verbose - set a sparse file cookie to print verbose errors
+ *
+ * @s - sparse file cookie
+ *
+ * Print verbose sparse file errors whenever using the sparse file cookie.
+ */
+void sparse_file_verbose(struct sparse_file *s);
+
+/**
+ * sparse_print_verbose - function called to print verbose errors
+ *
+ * By default, verbose errors will print to standard error.
+ * sparse_print_verbose may be overridden to log verbose errors somewhere else.
+ *
+ */
+extern void (*sparse_print_verbose)(const char *fmt, ...);
+
+#endif
diff --git a/libsparse/output_file.c b/libsparse/output_file.c
new file mode 100644
index 0000000..b5ae419
--- /dev/null
+++ b/libsparse/output_file.c
@@ -0,0 +1,772 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+
+#include <fcntl.h>
+#include <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+#include <zlib.h>
+
+#include "output_file.h"
+#include "sparse_format.h"
+#include "sparse_crc32.h"
+
+#ifndef USE_MINGW
+#include <sys/mman.h>
+#define O_BINARY 0
+#else
+#define ftruncate64 ftruncate
+#endif
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define ftruncate64 ftruncate
+#define mmap64 mmap
+#define off64_t off_t
+#endif
+
+#ifdef __BIONIC__
+extern void* __mmap2(void *, size_t, int, int, int, off_t);
+static inline void *mmap64(void *addr, size_t length, int prot, int flags,
+ int fd, off64_t offset)
+{
+ return __mmap2(addr, length, prot, flags, fd, offset >> 12);
+}
+#endif
+
+#define min(a, b) \
+ ({ typeof(a) _a = (a); typeof(b) _b = (b); (_a < _b) ? _a : _b; })
+
+#define SPARSE_HEADER_MAJOR_VER 1
+#define SPARSE_HEADER_MINOR_VER 0
+#define SPARSE_HEADER_LEN (sizeof(sparse_header_t))
+#define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
+
+#define container_of(inner, outer_t, elem) \
+ ((outer_t *)((char *)inner - offsetof(outer_t, elem)))
+
+struct output_file_ops {
+ int (*open)(struct output_file *, int fd);
+ int (*skip)(struct output_file *, int64_t);
+ int (*pad)(struct output_file *, int64_t);
+ int (*write)(struct output_file *, void *, int);
+ void (*close)(struct output_file *);
+};
+
+struct sparse_file_ops {
+ int (*write_data_chunk)(struct output_file *out, unsigned int len,
+ void *data);
+ int (*write_fill_chunk)(struct output_file *out, unsigned int len,
+ uint32_t fill_val);
+ int (*write_skip_chunk)(struct output_file *out, int64_t len);
+ int (*write_end_chunk)(struct output_file *out);
+};
+
+struct output_file {
+ int64_t cur_out_ptr;
+ unsigned int chunk_cnt;
+ uint32_t crc32;
+ struct output_file_ops *ops;
+ struct sparse_file_ops *sparse_ops;
+ int use_crc;
+ unsigned int block_size;
+ int64_t len;
+ char *zero_buf;
+ uint32_t *fill_buf;
+ char *buf;
+};
+
+struct output_file_gz {
+ struct output_file out;
+ gzFile gz_fd;
+};
+
+#define to_output_file_gz(_o) \
+ container_of((_o), struct output_file_gz, out)
+
+struct output_file_normal {
+ struct output_file out;
+ int fd;
+};
+
+#define to_output_file_normal(_o) \
+ container_of((_o), struct output_file_normal, out)
+
+struct output_file_callback {
+ struct output_file out;
+ void *priv;
+ int (*write)(void *priv, const void *buf, int len);
+};
+
+#define to_output_file_callback(_o) \
+ container_of((_o), struct output_file_callback, out)
+
+static int file_open(struct output_file *out, int fd)
+{
+ struct output_file_normal *outn = to_output_file_normal(out);
+
+ outn->fd = fd;
+ return 0;
+}
+
+static int file_skip(struct output_file *out, int64_t cnt)
+{
+ off64_t ret;
+ struct output_file_normal *outn = to_output_file_normal(out);
+
+ ret = lseek64(outn->fd, cnt, SEEK_CUR);
+ if (ret < 0) {
+ error_errno("lseek64");
+ return -1;
+ }
+ return 0;
+}
+
+static int file_pad(struct output_file *out, int64_t len)
+{
+ int ret;
+ struct output_file_normal *outn = to_output_file_normal(out);
+
+ ret = ftruncate64(outn->fd, len);
+ if (ret < 0) {
+ return -errno;
+ }
+
+ return 0;
+}
+
+static int file_write(struct output_file *out, void *data, int len)
+{
+ int ret;
+ struct output_file_normal *outn = to_output_file_normal(out);
+
+ ret = write(outn->fd, data, len);
+ if (ret < 0) {
+ error_errno("write");
+ return -1;
+ } else if (ret < len) {
+ error("incomplete write");
+ return -1;
+ }
+
+ return 0;
+}
+
+static void file_close(struct output_file *out)
+{
+ struct output_file_normal *outn = to_output_file_normal(out);
+
+ free(outn);
+}
+
+static struct output_file_ops file_ops = {
+ .open = file_open,
+ .skip = file_skip,
+ .pad = file_pad,
+ .write = file_write,
+ .close = file_close,
+};
+
+static int gz_file_open(struct output_file *out, int fd)
+{
+ struct output_file_gz *outgz = to_output_file_gz(out);
+
+ outgz->gz_fd = gzdopen(fd, "wb9");
+ if (!outgz->gz_fd) {
+ error_errno("gzopen");
+ return -errno;
+ }
+
+ return 0;
+}
+
+
+static int gz_file_skip(struct output_file *out, int64_t cnt)
+{
+ off64_t ret;
+ struct output_file_gz *outgz = to_output_file_gz(out);
+
+ ret = gzseek(outgz->gz_fd, cnt, SEEK_CUR);
+ if (ret < 0) {
+ error_errno("gzseek");
+ return -1;
+ }
+ return 0;
+}
+
+static int gz_file_pad(struct output_file *out, int64_t len)
+{
+ off64_t ret;
+ struct output_file_gz *outgz = to_output_file_gz(out);
+
+ ret = gztell(outgz->gz_fd);
+ if (ret < 0) {
+ return -1;
+ }
+
+ if (ret >= len) {
+ return 0;
+ }
+
+ ret = gzseek(outgz->gz_fd, len - 1, SEEK_SET);
+ if (ret < 0) {
+ return -1;
+ }
+
+ gzwrite(outgz->gz_fd, "", 1);
+
+ return 0;
+}
+
+static int gz_file_write(struct output_file *out, void *data, int len)
+{
+ int ret;
+ struct output_file_gz *outgz = to_output_file_gz(out);
+
+ ret = gzwrite(outgz->gz_fd, data, len);
+ if (ret < 0) {
+ error_errno("gzwrite");
+ return -1;
+ } else if (ret < len) {
+ error("incomplete gzwrite");
+ return -1;
+ }
+
+ return 0;
+}
+
+static void gz_file_close(struct output_file *out)
+{
+ struct output_file_gz *outgz = to_output_file_gz(out);
+
+ gzclose(outgz->gz_fd);
+ free(outgz);
+}
+
+static struct output_file_ops gz_file_ops = {
+ .open = gz_file_open,
+ .skip = gz_file_skip,
+ .pad = gz_file_pad,
+ .write = gz_file_write,
+ .close = gz_file_close,
+};
+
+static int callback_file_open(struct output_file *out, int fd)
+{
+ return 0;
+}
+
+static int callback_file_skip(struct output_file *out, int64_t off)
+{
+ struct output_file_callback *outc = to_output_file_callback(out);
+ int to_write;
+ int ret;
+
+ while (off > 0) {
+ to_write = min(off, (int64_t)INT_MAX);
+ ret = outc->write(outc->priv, NULL, to_write);
+ if (ret < 0) {
+ return ret;
+ }
+ off -= to_write;
+ }
+
+ return 0;
+}
+
+static int callback_file_pad(struct output_file *out, int64_t len)
+{
+ return -1;
+}
+
+static int callback_file_write(struct output_file *out, void *data, int len)
+{
+ int ret;
+ struct output_file_callback *outc = to_output_file_callback(out);
+
+ return outc->write(outc->priv, data, len);
+}
+
+static void callback_file_close(struct output_file *out)
+{
+ struct output_file_callback *outc = to_output_file_callback(out);
+
+ free(outc);
+}
+
+static struct output_file_ops callback_file_ops = {
+ .open = callback_file_open,
+ .skip = callback_file_skip,
+ .pad = callback_file_pad,
+ .write = callback_file_write,
+ .close = callback_file_close,
+};
+
+int read_all(int fd, void *buf, size_t len)
+{
+ size_t total = 0;
+ int ret;
+ char *ptr = buf;
+
+ while (total < len) {
+ ret = read(fd, ptr, len - total);
+
+ if (ret < 0)
+ return -errno;
+
+ if (ret == 0)
+ return -EINVAL;
+
+ ptr += ret;
+ total += ret;
+ }
+
+ return 0;
+}
+
+static int write_sparse_skip_chunk(struct output_file *out, int64_t skip_len)
+{
+ chunk_header_t chunk_header;
+ int ret, chunk;
+
+ if (skip_len % out->block_size) {
+ error("don't care size %llu is not a multiple of the block size %u",
+ skip_len, out->block_size);
+ return -1;
+ }
+
+ /* We are skipping data, so emit a don't care chunk. */
+ chunk_header.chunk_type = CHUNK_TYPE_DONT_CARE;
+ chunk_header.reserved1 = 0;
+ chunk_header.chunk_sz = skip_len / out->block_size;
+ chunk_header.total_sz = CHUNK_HEADER_LEN;
+ ret = out->ops->write(out, &chunk_header, sizeof(chunk_header));
+ if (ret < 0)
+ return -1;
+
+ out->cur_out_ptr += skip_len;
+ out->chunk_cnt++;
+
+ return 0;
+}
+
+static int write_sparse_fill_chunk(struct output_file *out, unsigned int len,
+ uint32_t fill_val)
+{
+ chunk_header_t chunk_header;
+ int rnd_up_len, zero_len, count;
+ int ret;
+ unsigned int i;
+
+ /* Round up the fill length to a multiple of the block size */
+ rnd_up_len = ALIGN(len, out->block_size);
+
+ /* Finally we can safely emit a chunk of data */
+ chunk_header.chunk_type = CHUNK_TYPE_FILL;
+ chunk_header.reserved1 = 0;
+ chunk_header.chunk_sz = rnd_up_len / out->block_size;
+ chunk_header.total_sz = CHUNK_HEADER_LEN + sizeof(fill_val);
+ ret = out->ops->write(out, &chunk_header, sizeof(chunk_header));
+
+ if (ret < 0)
+ return -1;
+ ret = out->ops->write(out, &fill_val, sizeof(fill_val));
+ if (ret < 0)
+ return -1;
+
+ if (out->use_crc) {
+ count = out->block_size / sizeof(uint32_t);
+ while (count--)
+ out->crc32 = sparse_crc32(out->crc32, &fill_val, sizeof(uint32_t));
+ }
+
+ out->cur_out_ptr += rnd_up_len;
+ out->chunk_cnt++;
+
+ return 0;
+}
+
+static int write_sparse_data_chunk(struct output_file *out, unsigned int len,
+ void *data)
+{
+ chunk_header_t chunk_header;
+ int rnd_up_len, zero_len;
+ int ret;
+
+ /* Round up the data length to a multiple of the block size */
+ rnd_up_len = ALIGN(len, out->block_size);
+ zero_len = rnd_up_len - len;
+
+ /* Finally we can safely emit a chunk of data */
+ chunk_header.chunk_type = CHUNK_TYPE_RAW;
+ chunk_header.reserved1 = 0;
+ chunk_header.chunk_sz = rnd_up_len / out->block_size;
+ chunk_header.total_sz = CHUNK_HEADER_LEN + rnd_up_len;
+ ret = out->ops->write(out, &chunk_header, sizeof(chunk_header));
+
+ if (ret < 0)
+ return -1;
+ ret = out->ops->write(out, data, len);
+ if (ret < 0)
+ return -1;
+ if (zero_len) {
+ ret = out->ops->write(out, out->zero_buf, zero_len);
+ if (ret < 0)
+ return -1;
+ }
+
+ if (out->use_crc) {
+ out->crc32 = sparse_crc32(out->crc32, data, len);
+ if (zero_len)
+ out->crc32 = sparse_crc32(out->crc32, out->zero_buf, zero_len);
+ }
+
+ out->cur_out_ptr += rnd_up_len;
+ out->chunk_cnt++;
+
+ return 0;
+}
+
+int write_sparse_end_chunk(struct output_file *out)
+{
+ chunk_header_t chunk_header;
+ int ret;
+
+ if (out->use_crc) {
+ chunk_header.chunk_type = CHUNK_TYPE_CRC32;
+ chunk_header.reserved1 = 0;
+ chunk_header.chunk_sz = 0;
+ chunk_header.total_sz = CHUNK_HEADER_LEN + 4;
+
+ ret = out->ops->write(out, &chunk_header, sizeof(chunk_header));
+ if (ret < 0) {
+ return ret;
+ }
+ out->ops->write(out, &out->crc32, 4);
+ if (ret < 0) {
+ return ret;
+ }
+
+ out->chunk_cnt++;
+ }
+
+ return 0;
+}
+
+static struct sparse_file_ops sparse_file_ops = {
+ .write_data_chunk = write_sparse_data_chunk,
+ .write_fill_chunk = write_sparse_fill_chunk,
+ .write_skip_chunk = write_sparse_skip_chunk,
+ .write_end_chunk = write_sparse_end_chunk,
+};
+
+static int write_normal_data_chunk(struct output_file *out, unsigned int len,
+ void *data)
+{
+ int ret;
+ unsigned int rnd_up_len = ALIGN(len, out->block_size);
+
+ ret = out->ops->write(out, data, len);
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (rnd_up_len > len) {
+ ret = out->ops->skip(out, rnd_up_len - len);
+ }
+
+ return ret;
+}
+
+static int write_normal_fill_chunk(struct output_file *out, unsigned int len,
+ uint32_t fill_val)
+{
+ int ret;
+ unsigned int i;
+ unsigned int write_len;
+
+ /* Initialize fill_buf with the fill_val */
+ for (i = 0; i < out->block_size / sizeof(uint32_t); i++) {
+ out->fill_buf[i] = fill_val;
+ }
+
+ while (len) {
+ write_len = min(len, out->block_size);
+ ret = out->ops->write(out, out->fill_buf, write_len);
+ if (ret < 0) {
+ return ret;
+ }
+
+ len -= write_len;
+ }
+
+ return 0;
+}
+
+static int write_normal_skip_chunk(struct output_file *out, int64_t len)
+{
+ return out->ops->skip(out, len);
+}
+
+int write_normal_end_chunk(struct output_file *out)
+{
+ return out->ops->pad(out, out->len);
+}
+
+static struct sparse_file_ops normal_file_ops = {
+ .write_data_chunk = write_normal_data_chunk,
+ .write_fill_chunk = write_normal_fill_chunk,
+ .write_skip_chunk = write_normal_skip_chunk,
+ .write_end_chunk = write_normal_end_chunk,
+};
+
+void output_file_close(struct output_file *out)
+{
+ int ret;
+
+ out->sparse_ops->write_end_chunk(out);
+ out->ops->close(out);
+}
+
+static int output_file_init(struct output_file *out, int block_size,
+ int64_t len, bool sparse, int chunks, bool crc)
+{
+ int ret;
+
+ out->len = len;
+ out->block_size = block_size;
+ out->cur_out_ptr = 0ll;
+ out->chunk_cnt = 0;
+ out->crc32 = 0;
+ out->use_crc = crc;
+
+ out->zero_buf = calloc(block_size, 1);
+ if (!out->zero_buf) {
+ error_errno("malloc zero_buf");
+ return -ENOMEM;
+ }
+
+ out->fill_buf = calloc(block_size, 1);
+ if (!out->fill_buf) {
+ error_errno("malloc fill_buf");
+ ret = -ENOMEM;
+ goto err_fill_buf;
+ }
+
+ if (sparse) {
+ out->sparse_ops = &sparse_file_ops;
+ } else {
+ out->sparse_ops = &normal_file_ops;
+ }
+
+ if (sparse) {
+ sparse_header_t sparse_header = {
+ .magic = SPARSE_HEADER_MAGIC,
+ .major_version = SPARSE_HEADER_MAJOR_VER,
+ .minor_version = SPARSE_HEADER_MINOR_VER,
+ .file_hdr_sz = SPARSE_HEADER_LEN,
+ .chunk_hdr_sz = CHUNK_HEADER_LEN,
+ .blk_sz = out->block_size,
+ .total_blks = out->len / out->block_size,
+ .total_chunks = chunks,
+ .image_checksum = 0
+ };
+
+ if (out->use_crc) {
+ sparse_header.total_chunks++;
+ }
+
+ ret = out->ops->write(out, &sparse_header, sizeof(sparse_header));
+ if (ret < 0) {
+ goto err_write;
+ }
+ }
+
+ return 0;
+
+err_write:
+ free(out->fill_buf);
+err_fill_buf:
+ free(out->zero_buf);
+ return ret;
+}
+
+static struct output_file *output_file_new_gz(void)
+{
+ struct output_file_gz *outgz = calloc(1, sizeof(struct output_file_gz));
+ if (!outgz) {
+ error_errno("malloc struct outgz");
+ return NULL;
+ }
+
+ outgz->out.ops = &gz_file_ops;
+
+ return &outgz->out;
+}
+
+static struct output_file *output_file_new_normal(void)
+{
+ struct output_file_normal *outn = calloc(1, sizeof(struct output_file_normal));
+ if (!outn) {
+ error_errno("malloc struct outn");
+ return NULL;
+ }
+
+ outn->out.ops = &file_ops;
+
+ return &outn->out;
+}
+
+struct output_file *output_file_open_callback(int (*write)(void *, const void *, int),
+ void *priv, unsigned int block_size, int64_t len, int gz, int sparse,
+ int chunks, int crc)
+{
+ int ret;
+ struct output_file_callback *outc;
+
+ outc = calloc(1, sizeof(struct output_file_callback));
+ if (!outc) {
+ error_errno("malloc struct outc");
+ return NULL;
+ }
+
+ outc->out.ops = &callback_file_ops;
+ outc->priv = priv;
+ outc->write = write;
+
+ ret = output_file_init(&outc->out, block_size, len, sparse, chunks, crc);
+ if (ret < 0) {
+ free(outc);
+ return NULL;
+ }
+
+ return &outc->out;
+}
+
+struct output_file *output_file_open_fd(int fd, unsigned int block_size, int64_t len,
+ int gz, int sparse, int chunks, int crc)
+{
+ int ret;
+ struct output_file *out;
+
+ if (gz) {
+ out = output_file_new_gz();
+ } else {
+ out = output_file_new_normal();
+ }
+
+ out->ops->open(out, fd);
+
+ ret = output_file_init(out, block_size, len, sparse, chunks, crc);
+ if (ret < 0) {
+ free(out);
+ return NULL;
+ }
+
+ return out;
+}
+
+/* Write a contiguous region of data blocks from a memory buffer */
+int write_data_chunk(struct output_file *out, unsigned int len, void *data)
+{
+ return out->sparse_ops->write_data_chunk(out, len, data);
+}
+
+/* Write a contiguous region of data blocks with a fill value */
+int write_fill_chunk(struct output_file *out, unsigned int len,
+ uint32_t fill_val)
+{
+ return out->sparse_ops->write_fill_chunk(out, len, fill_val);
+}
+
+int write_fd_chunk(struct output_file *out, unsigned int len,
+ int fd, int64_t offset)
+{
+ int ret;
+ int64_t aligned_offset;
+ int aligned_diff;
+ int buffer_size;
+ char *ptr;
+
+ aligned_offset = offset & ~(4096 - 1);
+ aligned_diff = offset - aligned_offset;
+ buffer_size = len + aligned_diff;
+
+#ifndef USE_MINGW
+ char *data = mmap64(NULL, buffer_size, PROT_READ, MAP_SHARED, fd,
+ aligned_offset);
+ if (data == MAP_FAILED) {
+ return -errno;
+ }
+ ptr = data + aligned_diff;
+#else
+ off64_t pos;
+ char *data = malloc(len);
+ if (!data) {
+ return -errno;
+ }
+ pos = lseek64(fd, offset, SEEK_SET);
+ if (pos < 0) {
+ return -errno;
+ }
+ ret = read_all(fd, data, len);
+ if (ret < 0) {
+ return ret;
+ }
+ ptr = data;
+#endif
+
+ ret = out->sparse_ops->write_data_chunk(out, len, ptr);
+
+#ifndef USE_MINGW
+ munmap(data, buffer_size);
+#else
+ free(data);
+#endif
+
+ return ret;
+}
+
+/* Write a contiguous region of data blocks from a file */
+int write_file_chunk(struct output_file *out, unsigned int len,
+ const char *file, int64_t offset)
+{
+ int ret;
+
+ int file_fd = open(file, O_RDONLY | O_BINARY);
+ if (file_fd < 0) {
+ return -errno;
+ }
+
+ ret = write_fd_chunk(out, len, file_fd, offset);
+
+ close(file_fd);
+
+ return ret;
+}
+
+int write_skip_chunk(struct output_file *out, int64_t len)
+{
+ return out->sparse_ops->write_skip_chunk(out, len);
+}
diff --git a/libsparse/output_file.h b/libsparse/output_file.h
new file mode 100644
index 0000000..474c1fc
--- /dev/null
+++ b/libsparse/output_file.h
@@ -0,0 +1,41 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _OUTPUT_FILE_H_
+#define _OUTPUT_FILE_H_
+
+#include <sparse/sparse.h>
+
+struct output_file;
+
+struct output_file *output_file_open_fd(int fd, unsigned int block_size, int64_t len,
+ int gz, int sparse, int chunks, int crc);
+struct output_file *output_file_open_callback(int (*write)(void *, const void *, int),
+ void *priv, unsigned int block_size, int64_t len, int gz, int sparse,
+ int chunks, int crc);
+int write_data_chunk(struct output_file *out, unsigned int len, void *data);
+int write_fill_chunk(struct output_file *out, unsigned int len,
+ uint32_t fill_val);
+int write_file_chunk(struct output_file *out, unsigned int len,
+ const char *file, int64_t offset);
+int write_fd_chunk(struct output_file *out, unsigned int len,
+ int fd, int64_t offset);
+int write_skip_chunk(struct output_file *out, int64_t len);
+void output_file_close(struct output_file *out);
+
+int read_all(int fd, void *buf, size_t len);
+
+#endif
diff --git a/libsparse/simg2img.c b/libsparse/simg2img.c
new file mode 100644
index 0000000..95e9b5b
--- /dev/null
+++ b/libsparse/simg2img.c
@@ -0,0 +1,89 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <sparse/sparse.h>
+
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#ifndef O_BINARY
+#define O_BINARY 0
+#endif
+
+void usage()
+{
+ fprintf(stderr, "Usage: simg2img <sparse_image_files> <raw_image_file>\n");
+}
+
+int main(int argc, char *argv[])
+{
+ int in;
+ int out;
+ int i;
+ int ret;
+ struct sparse_file *s;
+
+ if (argc < 3) {
+ usage();
+ exit(-1);
+ }
+
+ out = open(argv[argc - 1], O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0664);
+ if (out < 0) {
+ fprintf(stderr, "Cannot open output file %s\n", argv[argc - 1]);
+ exit(-1);
+ }
+
+ for (i = 1; i < argc - 1; i++) {
+ if (strcmp(argv[i], "-") == 0) {
+ in = STDIN_FILENO;
+ } else {
+ in = open(argv[i], O_RDONLY | O_BINARY);
+ if (in < 0) {
+ fprintf(stderr, "Cannot open input file %s\n", argv[i]);
+ exit(-1);
+ }
+ }
+
+ s = sparse_file_import(in, true, false);
+ if (!s) {
+ fprintf(stderr, "Failed to read sparse file\n");
+ exit(-1);
+ }
+
+ lseek(out, SEEK_SET, 0);
+
+ ret = sparse_file_write(s, out, false, false, false);
+ if (ret < 0) {
+ fprintf(stderr, "Cannot write output file\n");
+ exit(-1);
+ }
+ sparse_file_destroy(s);
+ close(in);
+ }
+
+ close(out);
+
+ exit(0);
+}
+
diff --git a/libsparse/simg2simg.c b/libsparse/simg2simg.c
new file mode 100644
index 0000000..5f9ccf6
--- /dev/null
+++ b/libsparse/simg2simg.c
@@ -0,0 +1,115 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+#define _GNU_SOURCE
+
+#include <fcntl.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <sparse/sparse.h>
+
+#ifndef O_BINARY
+#define O_BINARY 0
+#endif
+
+void usage()
+{
+ fprintf(stderr, "Usage: simg2simg <sparse image file> <sparse_image_file> <max_size>\n");
+}
+
+int main(int argc, char *argv[])
+{
+ int in;
+ int out;
+ int i;
+ int ret;
+ struct sparse_file *s;
+ int64_t max_size;
+ struct sparse_file **out_s;
+ int files;
+ char filename[4096];
+
+ if (argc != 4) {
+ usage();
+ exit(-1);
+ }
+
+ max_size = atoll(argv[3]);
+
+ in = open(argv[1], O_RDONLY | O_BINARY);
+ if (in < 0) {
+ fprintf(stderr, "Cannot open input file %s\n", argv[1]);
+ exit(-1);
+ }
+
+ s = sparse_file_import(in, true, false);
+ if (!s) {
+ fprintf(stderr, "Failed to import sparse file\n");
+ exit(-1);
+ }
+
+ files = sparse_file_resparse(s, max_size, NULL, 0);
+ if (files < 0) {
+ fprintf(stderr, "Failed to resparse\n");
+ exit(-1);
+ }
+
+ out_s = calloc(sizeof(struct sparse_file *), files);
+ if (!out_s) {
+ fprintf(stderr, "Failed to allocate sparse file array\n");
+ exit(-1);
+ }
+
+ files = sparse_file_resparse(s, max_size, out_s, files);
+ if (files < 0) {
+ fprintf(stderr, "Failed to resparse\n");
+ exit(-1);
+ }
+
+ for (i = 0; i < files; i++) {
+ ret = snprintf(filename, sizeof(filename), "%s.%d", argv[2], i);
+ if (ret >= (int)sizeof(filename)) {
+ fprintf(stderr, "Filename too long\n");
+ exit(-1);
+ }
+
+ out = open(filename, O_WRONLY | O_CREAT | O_TRUNC | O_BINARY, 0664);
+ if (out < 0) {
+ fprintf(stderr, "Cannot open output file %s\n", argv[2]);
+ exit(-1);
+ }
+
+ ret = sparse_file_write(out_s[i], out, false, true, false);
+ if (ret) {
+ fprintf(stderr, "Failed to write sparse file\n");
+ exit(-1);
+ }
+ close(out);
+ }
+
+ close(in);
+
+ exit(0);
+}
diff --git a/libsparse/simg_dump.py b/libsparse/simg_dump.py
new file mode 100755
index 0000000..6ece31d
--- /dev/null
+++ b/libsparse/simg_dump.py
@@ -0,0 +1,169 @@
+#! /usr/bin/env python
+
+# Copyright (C) 2012 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+from __future__ import print_function
+import getopt, posixpath, signal, struct, sys
+
+def usage(argv0):
+ print("""
+Usage: %s [-v] sparse_image_file ...
+ -v verbose output
+""" % ( argv0 ))
+ sys.exit(2)
+
+def main():
+
+ signal.signal(signal.SIGPIPE, signal.SIG_DFL)
+
+ me = posixpath.basename(sys.argv[0])
+
+ # Parse the command line
+ verbose = 0 # -v
+ try:
+ opts, args = getopt.getopt(sys.argv[1:],
+ "v",
+ ["verbose"])
+ except getopt.GetoptError, e:
+ print(e)
+ usage(me)
+ for o, a in opts:
+ if o in ("-v", "--verbose"):
+ verbose += 1
+ else:
+ print("Unrecognized option \"%s\"" % (o))
+ usage(me)
+
+ if len(args) == 0:
+ print("No sparse_image_file specified")
+ usage(me)
+
+ for path in args:
+ FH = open(path, 'rb')
+ header_bin = FH.read(28)
+ header = struct.unpack("<I4H4I", header_bin)
+
+ magic = header[0]
+ major_version = header[1]
+ minor_version = header[2]
+ file_hdr_sz = header[3]
+ chunk_hdr_sz = header[4]
+ blk_sz = header[5]
+ total_blks = header[6]
+ total_chunks = header[7]
+ image_checksum = header[8]
+
+ if magic != 0xED26FF3A:
+ print("%s: %s: Magic should be 0xED26FF3A but is 0x%08X"
+ % (me, path, magic))
+ continue
+ if major_version != 1 or minor_version != 0:
+ print("%s: %s: I only know about version 1.0, but this is version %u.%u"
+ % (me, path, major_version, minor_version))
+ continue
+ if file_hdr_sz != 28:
+ print("%s: %s: The file header size was expected to be 28, but is %u."
+ % (me, path, file_hdr_sz))
+ continue
+ if chunk_hdr_sz != 12:
+ print("%s: %s: The chunk header size was expected to be 12, but is %u."
+ % (me, path, chunk_hdr_sz))
+ continue
+
+ print("%s: Total of %u %u-byte output blocks in %u input chunks."
+ % (path, total_blks, blk_sz, total_chunks))
+
+ if image_checksum != 0:
+ print("checksum=0x%08X" % (image_checksum))
+
+ if not verbose:
+ continue
+ print(" input_bytes output_blocks")
+ print("chunk offset number offset number")
+ offset = 0
+ for i in xrange(1,total_chunks+1):
+ header_bin = FH.read(12)
+ header = struct.unpack("<2H2I", header_bin)
+ chunk_type = header[0]
+ reserved1 = header[1]
+ chunk_sz = header[2]
+ total_sz = header[3]
+ data_sz = total_sz - 12
+
+ print("%4u %10u %10u %7u %7u" % (i, FH.tell(), data_sz, offset, chunk_sz),
+ end=" ")
+
+ if chunk_type == 0xCAC1:
+ if data_sz != (chunk_sz * blk_sz):
+ print("Raw chunk input size (%u) does not match output size (%u)"
+ % (data_sz, chunk_sz * blk_sz))
+ break;
+ else:
+ print("Raw data", end="")
+ FH.read(data_sz)
+ elif chunk_type == 0xCAC2:
+ if data_sz != 4:
+ print("Fill chunk should have 4 bytes of fill, but this has %u"
+ % (data_sz), end="")
+ break;
+ else:
+ fill_bin = FH.read(4)
+ fill = struct.unpack("<I", fill_bin)
+ print("Fill with 0x%08X" % (fill))
+ elif chunk_type == 0xCAC3:
+ if data_sz != 0:
+ print("Don't care chunk input size is non-zero (%u)" % (data_sz))
+ break;
+ else:
+ print("Don't care", end="")
+ elif chunk_type == 0xCAC4:
+ if data_sz != 4:
+ print("CRC32 chunk should have 4 bytes of CRC, but this has %u"
+ % (data_sz), end="")
+ break;
+ else:
+ crc_bin = FH.read(4)
+ crc = struct.unpack("<I", crc)
+ print("Unverified CRC32 0x%08X" % (crc))
+ else:
+ print("Unknown chunk type 0x%04X" % (chunk_type), end="")
+ break;
+
+ if verbose > 1:
+ header = struct.unpack("<12B", header_bin)
+ print(" (%02X%02X %02X%02X %02X%02X%02X%02X %02X%02X%02X%02X)"
+ % (header[0], header[1], header[2], header[3],
+ header[4], header[5], header[6], header[7],
+ header[8], header[9], header[10], header[11]))
+ else:
+ print()
+
+ offset += chunk_sz
+
+ print(" %10u %7u End" % (FH.tell(), offset))
+
+ if total_blks != offset:
+ print("The header said we should have %u output blocks, but we saw %u"
+ % (total_blks, offset))
+
+ junk_len = len(FH.read())
+ if junk_len:
+ print("There were %u bytes of extra data at the end of the file."
+ % (junk_len))
+
+ sys.exit(0)
+
+if __name__ == "__main__":
+ main()
diff --git a/libsparse/sparse.c b/libsparse/sparse.c
new file mode 100644
index 0000000..189b4c0
--- /dev/null
+++ b/libsparse/sparse.c
@@ -0,0 +1,317 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <assert.h>
+#include <stdlib.h>
+
+#include <sparse/sparse.h>
+
+#include "sparse_file.h"
+
+#include "output_file.h"
+#include "backed_block.h"
+#include "sparse_defs.h"
+#include "sparse_format.h"
+
+struct sparse_file *sparse_file_new(unsigned int block_size, int64_t len)
+{
+ struct sparse_file *s = calloc(sizeof(struct sparse_file), 1);
+ if (!s) {
+ return NULL;
+ }
+
+ s->backed_block_list = backed_block_list_new(block_size);
+ if (!s->backed_block_list) {
+ free(s);
+ return NULL;
+ }
+
+ s->block_size = block_size;
+ s->len = len;
+
+ return s;
+}
+
+void sparse_file_destroy(struct sparse_file *s)
+{
+ backed_block_list_destroy(s->backed_block_list);
+ free(s);
+}
+
+int sparse_file_add_data(struct sparse_file *s,
+ void *data, unsigned int len, unsigned int block)
+{
+ return backed_block_add_data(s->backed_block_list, data, len, block);
+}
+
+int sparse_file_add_fill(struct sparse_file *s,
+ uint32_t fill_val, unsigned int len, unsigned int block)
+{
+ return backed_block_add_fill(s->backed_block_list, fill_val, len, block);
+}
+
+int sparse_file_add_file(struct sparse_file *s,
+ const char *filename, int64_t file_offset, unsigned int len,
+ unsigned int block)
+{
+ return backed_block_add_file(s->backed_block_list, filename, file_offset,
+ len, block);
+}
+
+int sparse_file_add_fd(struct sparse_file *s,
+ int fd, int64_t file_offset, unsigned int len, unsigned int block)
+{
+ return backed_block_add_fd(s->backed_block_list, fd, file_offset,
+ len, block);
+}
+unsigned int sparse_count_chunks(struct sparse_file *s)
+{
+ struct backed_block *bb;
+ unsigned int last_block = 0;
+ unsigned int chunks = 0;
+
+ for (bb = backed_block_iter_new(s->backed_block_list); bb;
+ bb = backed_block_iter_next(bb)) {
+ if (backed_block_block(bb) > last_block) {
+ /* If there is a gap between chunks, add a skip chunk */
+ chunks++;
+ }
+ chunks++;
+ last_block = backed_block_block(bb) +
+ DIV_ROUND_UP(backed_block_len(bb), s->block_size);
+ }
+ if (last_block < DIV_ROUND_UP(s->len, s->block_size)) {
+ chunks++;
+ }
+
+ return chunks;
+}
+
+static void sparse_file_write_block(struct output_file *out,
+ struct backed_block *bb)
+{
+ switch (backed_block_type(bb)) {
+ case BACKED_BLOCK_DATA:
+ write_data_chunk(out, backed_block_len(bb), backed_block_data(bb));
+ break;
+ case BACKED_BLOCK_FILE:
+ write_file_chunk(out, backed_block_len(bb),
+ backed_block_filename(bb), backed_block_file_offset(bb));
+ break;
+ case BACKED_BLOCK_FD:
+ write_fd_chunk(out, backed_block_len(bb),
+ backed_block_fd(bb), backed_block_file_offset(bb));
+ break;
+ case BACKED_BLOCK_FILL:
+ write_fill_chunk(out, backed_block_len(bb),
+ backed_block_fill_val(bb));
+ break;
+ }
+}
+
+static int write_all_blocks(struct sparse_file *s, struct output_file *out)
+{
+ struct backed_block *bb;
+ unsigned int last_block = 0;
+ int64_t pad;
+
+ for (bb = backed_block_iter_new(s->backed_block_list); bb;
+ bb = backed_block_iter_next(bb)) {
+ if (backed_block_block(bb) > last_block) {
+ unsigned int blocks = backed_block_block(bb) - last_block;
+ write_skip_chunk(out, (int64_t)blocks * s->block_size);
+ }
+ sparse_file_write_block(out, bb);
+ last_block = backed_block_block(bb) +
+ DIV_ROUND_UP(backed_block_len(bb), s->block_size);
+ }
+
+ pad = s->len - last_block * s->block_size;
+ assert(pad >= 0);
+ if (pad > 0) {
+ write_skip_chunk(out, pad);
+ }
+
+ return 0;
+}
+
+int sparse_file_write(struct sparse_file *s, int fd, bool gz, bool sparse,
+ bool crc)
+{
+ int ret;
+ int chunks;
+ struct output_file *out;
+
+ chunks = sparse_count_chunks(s);
+ out = output_file_open_fd(fd, s->block_size, s->len, gz, sparse, chunks, crc);
+
+ if (!out)
+ return -ENOMEM;
+
+ ret = write_all_blocks(s, out);
+
+ output_file_close(out);
+
+ return ret;
+}
+
+int sparse_file_callback(struct sparse_file *s, bool sparse, bool crc,
+ int (*write)(void *priv, const void *data, int len), void *priv)
+{
+ int ret;
+ int chunks;
+ struct output_file *out;
+
+ chunks = sparse_count_chunks(s);
+ out = output_file_open_callback(write, priv, s->block_size, s->len, false,
+ sparse, chunks, crc);
+
+ if (!out)
+ return -ENOMEM;
+
+ ret = write_all_blocks(s, out);
+
+ output_file_close(out);
+
+ return ret;
+}
+
+static int out_counter_write(void *priv, const void *data, int len)
+{
+ int64_t *count = priv;
+ *count += len;
+ return 0;
+}
+
+int64_t sparse_file_len(struct sparse_file *s, bool sparse, bool crc)
+{
+ int ret;
+ int chunks = sparse_count_chunks(s);
+ int64_t count = 0;
+ struct output_file *out;
+
+ out = output_file_open_callback(out_counter_write, &count,
+ s->block_size, s->len, false, sparse, chunks, crc);
+ if (!out) {
+ return -1;
+ }
+
+ ret = write_all_blocks(s, out);
+
+ output_file_close(out);
+
+ if (ret < 0) {
+ return -1;
+ }
+
+ return count;
+}
+
+static struct backed_block *move_chunks_up_to_len(struct sparse_file *from,
+ struct sparse_file *to, unsigned int len)
+{
+ int64_t count = 0;
+ struct output_file *out_counter;
+ struct backed_block *last_bb = NULL;
+ struct backed_block *bb;
+ struct backed_block *start;
+ int64_t file_len = 0;
+
+ /*
+ * overhead is sparse file header, initial skip chunk, split chunk, end
+ * skip chunk, and crc chunk.
+ */
+ int overhead = sizeof(sparse_header_t) + 4 * sizeof(chunk_header_t) +
+ sizeof(uint32_t);
+ len -= overhead;
+
+ start = backed_block_iter_new(from->backed_block_list);
+ out_counter = output_file_open_callback(out_counter_write, &count,
+ to->block_size, to->len, false, true, 0, false);
+ if (!out_counter) {
+ return NULL;
+ }
+
+ for (bb = start; bb; bb = backed_block_iter_next(bb)) {
+ count = 0;
+ /* will call out_counter_write to update count */
+ sparse_file_write_block(out_counter, bb);
+ if (file_len + count > len) {
+ /*
+ * If the remaining available size is more than 1/8th of the
+ * requested size, split the chunk. Results in sparse files that
+ * are at least 7/8ths of the requested size
+ */
+ if (!last_bb || (len - file_len > (len / 8))) {
+ backed_block_split(from->backed_block_list, bb, len - file_len);
+ last_bb = bb;
+ }
+ goto out;
+ }
+ file_len += count;
+ last_bb = bb;
+ }
+
+out:
+ backed_block_list_move(from->backed_block_list,
+ to->backed_block_list, start, last_bb);
+
+ output_file_close(out_counter);
+
+ return bb;
+}
+
+int sparse_file_resparse(struct sparse_file *in_s, unsigned int max_len,
+ struct sparse_file **out_s, int out_s_count)
+{
+ struct backed_block *bb;
+ unsigned int overhead;
+ struct sparse_file *s;
+ struct sparse_file *tmp;
+ int c = 0;
+
+ tmp = sparse_file_new(in_s->block_size, in_s->len);
+ if (!tmp) {
+ return -ENOMEM;
+ }
+
+ do {
+ s = sparse_file_new(in_s->block_size, in_s->len);
+
+ bb = move_chunks_up_to_len(in_s, s, max_len);
+
+ if (c < out_s_count) {
+ out_s[c] = s;
+ } else {
+ backed_block_list_move(s->backed_block_list, tmp->backed_block_list,
+ NULL, NULL);
+ sparse_file_destroy(s);
+ }
+ c++;
+ } while (bb);
+
+ backed_block_list_move(tmp->backed_block_list, in_s->backed_block_list,
+ NULL, NULL);
+
+ sparse_file_destroy(tmp);
+
+ return c;
+}
+
+void sparse_file_verbose(struct sparse_file *s)
+{
+ s->verbose = true;
+}
diff --git a/libsparse/sparse_crc32.c b/libsparse/sparse_crc32.c
new file mode 100644
index 0000000..38bfe4a
--- /dev/null
+++ b/libsparse/sparse_crc32.c
@@ -0,0 +1,111 @@
+/*-
+ * COPYRIGHT (C) 1986 Gary S. Brown. You may use this program, or
+ * code or tables extracted from it, as desired without restriction.
+ */
+
+/*
+ * First, the polynomial itself and its table of feedback terms. The
+ * polynomial is
+ * X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+X^0
+ *
+ * Note that we take it "backwards" and put the highest-order term in
+ * the lowest-order bit. The X^32 term is "implied"; the LSB is the
+ * X^31 term, etc. The X^0 term (usually shown as "+1") results in
+ * the MSB being 1
+ *
+ * Note that the usual hardware shift register implementation, which
+ * is what we're using (we're merely optimizing it by doing eight-bit
+ * chunks at a time) shifts bits into the lowest-order term. In our
+ * implementation, that means shifting towards the right. Why do we
+ * do it this way? Because the calculated CRC must be transmitted in
+ * order from highest-order term to lowest-order term. UARTs transmit
+ * characters in order from LSB to MSB. By storing the CRC this way
+ * we hand it to the UART in the order low-byte to high-byte; the UART
+ * sends each low-bit to hight-bit; and the result is transmission bit
+ * by bit from highest- to lowest-order term without requiring any bit
+ * shuffling on our part. Reception works similarly
+ *
+ * The feedback terms table consists of 256, 32-bit entries. Notes
+ *
+ * The table can be generated at runtime if desired; code to do so
+ * is shown later. It might not be obvious, but the feedback
+ * terms simply represent the results of eight shift/xor opera
+ * tions for all combinations of data and CRC register values
+ *
+ * The values must be right-shifted by eight bits by the "updcrc
+ * logic; the shift must be unsigned (bring in zeroes). On some
+ * hardware you could probably optimize the shift in assembler by
+ * using byte-swap instructions
+ * polynomial $edb88320
+ *
+ *
+ * CRC32 code derived from work by Gary S. Brown.
+ */
+
+/* Code taken from FreeBSD 8 */
+#include <stdint.h>
+
+static uint32_t crc32_tab[] = {
+ 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
+ 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
+ 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
+ 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
+ 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
+ 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
+ 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
+ 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
+ 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
+ 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
+ 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
+ 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
+ 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
+ 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
+ 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
+ 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
+ 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
+ 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
+ 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
+ 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
+ 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
+ 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
+ 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
+ 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
+ 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
+ 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
+ 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
+ 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
+ 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
+ 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
+ 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
+ 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
+ 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
+ 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
+ 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
+ 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
+ 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
+ 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
+ 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
+ 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
+ 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
+ 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
+ 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
+};
+
+/*
+ * A function that calculates the CRC-32 based on the table above is
+ * given below for documentation purposes. An equivalent implementation
+ * of this function that's actually used in the kernel can be found
+ * in sys/libkern.h, where it can be inlined.
+ */
+
+uint32_t sparse_crc32(uint32_t crc_in, const void *buf, int size)
+{
+ const uint8_t *p = buf;
+ uint32_t crc;
+
+ crc = crc_in ^ ~0U;
+ while (size--)
+ crc = crc32_tab[(crc ^ *p++) & 0xFF] ^ (crc >> 8);
+ return crc ^ ~0U;
+}
+
diff --git a/libsparse/sparse_crc32.h b/libsparse/sparse_crc32.h
new file mode 100644
index 0000000..cad8a86
--- /dev/null
+++ b/libsparse/sparse_crc32.h
@@ -0,0 +1,20 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdint.h>
+
+uint32_t sparse_crc32(uint32_t crc, const void *buf, size_t size);
+
diff --git a/libsparse/sparse_defs.h b/libsparse/sparse_defs.h
new file mode 100644
index 0000000..b99cfd5
--- /dev/null
+++ b/libsparse/sparse_defs.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_DEFS_
+#define _LIBSPARSE_SPARSE_DEFS_
+
+#include <errno.h>
+#include <stdio.h>
+
+#define __le64 u64
+#define __le32 u32
+#define __le16 u16
+
+#define __be64 u64
+#define __be32 u32
+#define __be16 u16
+
+#define __u64 u64
+#define __u32 u32
+#define __u16 u16
+#define __u8 u8
+
+typedef unsigned long long u64;
+typedef signed long long s64;
+typedef unsigned int u32;
+typedef unsigned short int u16;
+typedef unsigned char u8;
+
+#define DIV_ROUND_UP(x, y) (((x) + (y) - 1)/(y))
+#define ALIGN(x, y) ((y) * DIV_ROUND_UP((x), (y)))
+#define ALIGN_DOWN(x, y) ((y) * ((x) / (y)))
+
+#define error(fmt, args...) do { fprintf(stderr, "error: %s: " fmt "\n", __func__, ## args); } while (0)
+#define error_errno(s, args...) error(s ": %s", ##args, strerror(errno))
+
+#endif
diff --git a/libsparse/sparse_err.c b/libsparse/sparse_err.c
new file mode 100644
index 0000000..0f392ad
--- /dev/null
+++ b/libsparse/sparse_err.c
@@ -0,0 +1,33 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <sparse/sparse.h>
+
+#include <stdarg.h>
+#include <stdio.h>
+#include <unistd.h>
+
+void sparse_default_print(const char *fmt, ...)
+{
+ va_list argp;
+
+ va_start(argp, fmt);
+ vfprintf(stderr, fmt, argp);
+ va_end(argp);
+}
+
+void (*sparse_print_error)(const char *fmt, ...) = sparse_default_print;
+void (*sparse_print_verbose)(const char *fmt, ...) = sparse_default_print;
diff --git a/libsparse/sparse_file.h b/libsparse/sparse_file.h
new file mode 100644
index 0000000..91a12e6
--- /dev/null
+++ b/libsparse/sparse_file.h
@@ -0,0 +1,32 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_FILE_H_
+#define _LIBSPARSE_SPARSE_FILE_H_
+
+#include <sparse/sparse.h>
+
+struct sparse_file {
+ unsigned int block_size;
+ int64_t len;
+ bool verbose;
+
+ struct backed_block_list *backed_block_list;
+ struct output_file *out;
+};
+
+
+#endif /* _LIBSPARSE_SPARSE_FILE_H_ */
diff --git a/libsparse/sparse_format.h b/libsparse/sparse_format.h
new file mode 100644
index 0000000..c41f12a
--- /dev/null
+++ b/libsparse/sparse_format.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _LIBSPARSE_SPARSE_FORMAT_H_
+#define _LIBSPARSE_SPARSE_FORMAT_H_
+#include "sparse_defs.h"
+
+typedef struct sparse_header {
+ __le32 magic; /* 0xed26ff3a */
+ __le16 major_version; /* (0x1) - reject images with higher major versions */
+ __le16 minor_version; /* (0x0) - allow images with higer minor versions */
+ __le16 file_hdr_sz; /* 28 bytes for first revision of the file format */
+ __le16 chunk_hdr_sz; /* 12 bytes for first revision of the file format */
+ __le32 blk_sz; /* block size in bytes, must be a multiple of 4 (4096) */
+ __le32 total_blks; /* total blocks in the non-sparse output image */
+ __le32 total_chunks; /* total chunks in the sparse input image */
+ __le32 image_checksum; /* CRC32 checksum of the original data, counting "don't care" */
+ /* as 0. Standard 802.3 polynomial, use a Public Domain */
+ /* table implementation */
+} sparse_header_t;
+
+#define SPARSE_HEADER_MAGIC 0xed26ff3a
+
+#define CHUNK_TYPE_RAW 0xCAC1
+#define CHUNK_TYPE_FILL 0xCAC2
+#define CHUNK_TYPE_DONT_CARE 0xCAC3
+#define CHUNK_TYPE_CRC32 0xCAC4
+
+typedef struct chunk_header {
+ __le16 chunk_type; /* 0xCAC1 -> raw; 0xCAC2 -> fill; 0xCAC3 -> don't care */
+ __le16 reserved1;
+ __le32 chunk_sz; /* in blocks in output image */
+ __le32 total_sz; /* in bytes of chunk input file including chunk header and data */
+} chunk_header_t;
+
+/* Following a Raw or Fill or CRC32 chunk is data.
+ * For a Raw chunk, it's the data in chunk_sz * blk_sz.
+ * For a Fill chunk, it's 4 bytes of the fill data.
+ * For a CRC32 chunk, it's 4 bytes of CRC32
+ */
+
+#endif
diff --git a/libsparse/sparse_read.c b/libsparse/sparse_read.c
new file mode 100644
index 0000000..704bcfa
--- /dev/null
+++ b/libsparse/sparse_read.c
@@ -0,0 +1,509 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define _GNU_SOURCE
+#define _FILE_OFFSET_BITS 64
+#define _LARGEFILE64_SOURCE 1
+
+#include <fcntl.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <sparse/sparse.h>
+
+#include "sparse_crc32.h"
+#include "sparse_file.h"
+#include "sparse_format.h"
+
+#if defined(__APPLE__) && defined(__MACH__)
+#define lseek64 lseek
+#define off64_t off_t
+#endif
+
+#define SPARSE_HEADER_MAJOR_VER 1
+#define SPARSE_HEADER_LEN (sizeof(sparse_header_t))
+#define CHUNK_HEADER_LEN (sizeof(chunk_header_t))
+
+#define COPY_BUF_SIZE (1024U*1024U)
+static char *copybuf;
+
+#define min(a, b) \
+ ({ typeof(a) _a = (a); typeof(b) _b = (b); (_a < _b) ? _a : _b; })
+
+static void verbose_error(bool verbose, int err, const char *fmt, ...)
+{
+ char *s = "";
+ char *at = "";
+ if (fmt) {
+ va_list argp;
+ int size;
+
+ va_start(argp, fmt);
+ size = vsnprintf(NULL, 0, fmt, argp);
+ va_end(argp);
+
+ if (size < 0) {
+ return;
+ }
+
+ at = malloc(size + 1);
+ if (at == NULL) {
+ return;
+ }
+
+ va_start(argp, fmt);
+ vsnprintf(at, size, fmt, argp);
+ va_end(argp);
+ at[size] = 0;
+ s = " at ";
+ }
+ if (verbose) {
+#ifndef USE_MINGW
+ if (err == -EOVERFLOW) {
+ sparse_print_verbose("EOF while reading file%s%s\n", s, at);
+ } else
+#endif
+ if (err == -EINVAL) {
+ sparse_print_verbose("Invalid sparse file format%s%s\n", s, at);
+ } else if (err == -ENOMEM) {
+ sparse_print_verbose("Failed allocation while reading file%s%s\n",
+ s, at);
+ } else {
+ sparse_print_verbose("Unknown error %d%s%s\n", err, s, at);
+ }
+ }
+ if (fmt) {
+ free(at);
+ }
+}
+
+static int process_raw_chunk(struct sparse_file *s, unsigned int chunk_size,
+ int fd, int64_t offset, unsigned int blocks, unsigned int block,
+ uint32_t *crc32)
+{
+ int ret;
+ int chunk;
+ unsigned int len = blocks * s->block_size;
+
+ if (chunk_size % s->block_size != 0) {
+ return -EINVAL;
+ }
+
+ if (chunk_size / s->block_size != blocks) {
+ return -EINVAL;
+ }
+
+ ret = sparse_file_add_fd(s, fd, offset, len, block);
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (crc32) {
+ while (len) {
+ chunk = min(len, COPY_BUF_SIZE);
+ ret = read_all(fd, copybuf, chunk);
+ if (ret < 0) {
+ return ret;
+ }
+ *crc32 = sparse_crc32(*crc32, copybuf, chunk);
+ len -= chunk;
+ }
+ } else {
+ lseek64(fd, len, SEEK_CUR);
+ }
+
+ return 0;
+}
+
+static int process_fill_chunk(struct sparse_file *s, unsigned int chunk_size,
+ int fd, unsigned int blocks, unsigned int block, uint32_t *crc32)
+{
+ int ret;
+ int chunk;
+ int64_t len = (int64_t)blocks * s->block_size;
+ uint32_t fill_val;
+ uint32_t *fillbuf;
+ unsigned int i;
+
+ if (chunk_size != sizeof(fill_val)) {
+ return -EINVAL;
+ }
+
+ ret = read_all(fd, &fill_val, sizeof(fill_val));
+ if (ret < 0) {
+ return ret;
+ }
+
+ ret = sparse_file_add_fill(s, fill_val, len, block);
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (crc32) {
+ /* Fill copy_buf with the fill value */
+ fillbuf = (uint32_t *)copybuf;
+ for (i = 0; i < (COPY_BUF_SIZE / sizeof(fill_val)); i++) {
+ fillbuf[i] = fill_val;
+ }
+
+ while (len) {
+ chunk = min(len, COPY_BUF_SIZE);
+ *crc32 = sparse_crc32(*crc32, copybuf, chunk);
+ len -= chunk;
+ }
+ }
+
+ return 0;
+}
+
+static int process_skip_chunk(struct sparse_file *s, unsigned int chunk_size,
+ int fd, unsigned int blocks, unsigned int block, uint32_t *crc32)
+{
+ int ret;
+ int chunk;
+ int64_t len = (int64_t)blocks * s->block_size;
+ uint32_t fill_val;
+ uint32_t *fillbuf;
+ unsigned int i;
+
+ if (chunk_size != 0) {
+ return -EINVAL;
+ }
+
+ if (crc32) {
+ memset(copybuf, 0, COPY_BUF_SIZE);
+
+ while (len) {
+ chunk = min(len, COPY_BUF_SIZE);
+ *crc32 = sparse_crc32(*crc32, copybuf, chunk);
+ len -= chunk;
+ }
+ }
+
+ return 0;
+}
+
+static int process_crc32_chunk(int fd, unsigned int chunk_size, uint32_t crc32)
+{
+ uint32_t file_crc32;
+ int ret;
+
+ if (chunk_size != sizeof(file_crc32)) {
+ return -EINVAL;
+ }
+
+ ret = read_all(fd, &file_crc32, sizeof(file_crc32));
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (file_crc32 != crc32) {
+ return -EINVAL;
+ }
+
+ return 0;
+}
+
+static int process_chunk(struct sparse_file *s, int fd, off64_t offset,
+ unsigned int chunk_hdr_sz, chunk_header_t *chunk_header,
+ unsigned int cur_block, uint32_t *crc_ptr)
+{
+ int ret;
+ unsigned int chunk_data_size;
+
+ chunk_data_size = chunk_header->total_sz - chunk_hdr_sz;
+
+ switch (chunk_header->chunk_type) {
+ case CHUNK_TYPE_RAW:
+ ret = process_raw_chunk(s, chunk_data_size, fd, offset,
+ chunk_header->chunk_sz, cur_block, crc_ptr);
+ if (ret < 0) {
+ verbose_error(s->verbose, ret, "data block at %lld", offset);
+ return ret;
+ }
+ return chunk_header->chunk_sz;
+ case CHUNK_TYPE_FILL:
+ ret = process_fill_chunk(s, chunk_data_size, fd,
+ chunk_header->chunk_sz, cur_block, crc_ptr);
+ if (ret < 0) {
+ verbose_error(s->verbose, ret, "fill block at %lld", offset);
+ return ret;
+ }
+ return chunk_header->chunk_sz;
+ case CHUNK_TYPE_DONT_CARE:
+ ret = process_skip_chunk(s, chunk_data_size, fd,
+ chunk_header->chunk_sz, cur_block, crc_ptr);
+ if (chunk_data_size != 0) {
+ if (ret < 0) {
+ verbose_error(s->verbose, ret, "skip block at %lld", offset);
+ return ret;
+ }
+ }
+ return chunk_header->chunk_sz;
+ case CHUNK_TYPE_CRC32:
+ ret = process_crc32_chunk(fd, chunk_data_size, *crc_ptr);
+ if (ret < 0) {
+ verbose_error(s->verbose, -EINVAL, "crc block at %lld",
+ offset);
+ return ret;
+ }
+ return 0;
+ default:
+ verbose_error(s->verbose, -EINVAL, "unknown block %04X at %lld",
+ chunk_header->chunk_type, offset);
+ }
+
+ return 0;
+}
+
+static int sparse_file_read_sparse(struct sparse_file *s, int fd, bool crc)
+{
+ int ret;
+ unsigned int i;
+ sparse_header_t sparse_header;
+ chunk_header_t chunk_header;
+ uint32_t crc32 = 0;
+ uint32_t *crc_ptr = 0;
+ unsigned int cur_block = 0;
+ off64_t offset;
+
+ if (!copybuf) {
+ copybuf = malloc(COPY_BUF_SIZE);
+ }
+
+ if (!copybuf) {
+ return -ENOMEM;
+ }
+
+ if (crc) {
+ crc_ptr = &crc32;
+ }
+
+ ret = read_all(fd, &sparse_header, sizeof(sparse_header));
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (sparse_header.magic != SPARSE_HEADER_MAGIC) {
+ return -EINVAL;
+ }
+
+ if (sparse_header.major_version != SPARSE_HEADER_MAJOR_VER) {
+ return -EINVAL;
+ }
+
+ if (sparse_header.file_hdr_sz < SPARSE_HEADER_LEN) {
+ return -EINVAL;
+ }
+
+ if (sparse_header.chunk_hdr_sz < sizeof(chunk_header)) {
+ return -EINVAL;
+ }
+
+ if (sparse_header.file_hdr_sz > SPARSE_HEADER_LEN) {
+ /* Skip the remaining bytes in a header that is longer than
+ * we expected.
+ */
+ lseek64(fd, sparse_header.file_hdr_sz - SPARSE_HEADER_LEN, SEEK_CUR);
+ }
+
+ for (i = 0; i < sparse_header.total_chunks; i++) {
+ ret = read_all(fd, &chunk_header, sizeof(chunk_header));
+ if (ret < 0) {
+ return ret;
+ }
+
+ if (sparse_header.chunk_hdr_sz > CHUNK_HEADER_LEN) {
+ /* Skip the remaining bytes in a header that is longer than
+ * we expected.
+ */
+ lseek64(fd, sparse_header.chunk_hdr_sz - CHUNK_HEADER_LEN, SEEK_CUR);
+ }
+
+ offset = lseek64(fd, 0, SEEK_CUR);
+
+ ret = process_chunk(s, fd, offset, sparse_header.chunk_hdr_sz, &chunk_header,
+ cur_block, crc_ptr);
+ if (ret < 0) {
+ return ret;
+ }
+
+ cur_block += ret;
+ }
+
+ if (sparse_header.total_blks != cur_block) {
+ return -EINVAL;
+ }
+
+ return 0;
+}
+
+static int sparse_file_read_normal(struct sparse_file *s, int fd)
+{
+ int ret;
+ uint32_t *buf = malloc(s->block_size);
+ unsigned int block = 0;
+ int64_t remain = s->len;
+ int64_t offset = 0;
+ unsigned int to_read;
+ char *ptr;
+ unsigned int i;
+ bool sparse_block;
+
+ if (!buf) {
+ return -ENOMEM;
+ }
+
+ while (remain > 0) {
+ to_read = min(remain, s->block_size);
+ ret = read_all(fd, buf, to_read);
+ if (ret < 0) {
+ error("failed to read sparse file");
+ return ret;
+ }
+
+ if (to_read == s->block_size) {
+ sparse_block = true;
+ for (i = 1; i < s->block_size / sizeof(uint32_t); i++) {
+ if (buf[0] != buf[i]) {
+ sparse_block = false;
+ break;
+ }
+ }
+ } else {
+ sparse_block = false;
+ }
+
+ if (sparse_block) {
+ /* TODO: add flag to use skip instead of fill for buf[0] == 0 */
+ sparse_file_add_fill(s, buf[0], to_read, block);
+ } else {
+ sparse_file_add_fd(s, fd, offset, to_read, block);
+ }
+
+ remain -= to_read;
+ offset += to_read;
+ block++;
+ }
+
+ return 0;
+}
+
+int sparse_file_read(struct sparse_file *s, int fd, bool sparse, bool crc)
+{
+ if (crc && !sparse) {
+ return -EINVAL;
+ }
+
+ if (sparse) {
+ return sparse_file_read_sparse(s, fd, crc);
+ } else {
+ return sparse_file_read_normal(s, fd);
+ }
+}
+
+struct sparse_file *sparse_file_import(int fd, bool verbose, bool crc)
+{
+ int ret;
+ sparse_header_t sparse_header;
+ int64_t len;
+ struct sparse_file *s;
+
+ ret = read_all(fd, &sparse_header, sizeof(sparse_header));
+ if (ret < 0) {
+ verbose_error(verbose, ret, "header");
+ return NULL;
+ }
+
+ if (sparse_header.magic != SPARSE_HEADER_MAGIC) {
+ verbose_error(verbose, -EINVAL, "header magic");
+ return NULL;
+ }
+
+ if (sparse_header.major_version != SPARSE_HEADER_MAJOR_VER) {
+ verbose_error(verbose, -EINVAL, "header major version");
+ return NULL;
+ }
+
+ if (sparse_header.file_hdr_sz < SPARSE_HEADER_LEN) {
+ return NULL;
+ }
+
+ if (sparse_header.chunk_hdr_sz < sizeof(chunk_header_t)) {
+ return NULL;
+ }
+
+ len = (int64_t)sparse_header.total_blks * sparse_header.blk_sz;
+ s = sparse_file_new(sparse_header.blk_sz, len);
+ if (!s) {
+ verbose_error(verbose, -EINVAL, NULL);
+ return NULL;
+ }
+
+ ret = lseek64(fd, 0, SEEK_SET);
+ if (ret < 0) {
+ verbose_error(verbose, ret, "seeking");
+ sparse_file_destroy(s);
+ return NULL;
+ }
+
+ s->verbose = verbose;
+
+ ret = sparse_file_read(s, fd, true, crc);
+ if (ret < 0) {
+ sparse_file_destroy(s);
+ return NULL;
+ }
+
+ return s;
+}
+
+struct sparse_file *sparse_file_import_auto(int fd, bool crc)
+{
+ struct sparse_file *s;
+ int64_t len;
+ int ret;
+
+ s = sparse_file_import(fd, true, crc);
+ if (s) {
+ return s;
+ }
+
+ len = lseek64(fd, 0, SEEK_END);
+ if (len < 0) {
+ return NULL;
+ }
+
+ lseek64(fd, 0, SEEK_SET);
+
+ s = sparse_file_new(4096, len);
+ if (!s) {
+ return NULL;
+ }
+
+ ret = sparse_file_read_normal(s, fd);
+ if (ret < 0) {
+ sparse_file_destroy(s);
+ return NULL;
+ }
+
+ return s;
+}
diff --git a/rootdir/init.rc b/rootdir/init.rc
index 24200d0..8f692ac 100644
--- a/rootdir/init.rc
+++ b/rootdir/init.rc
@@ -32,7 +32,7 @@
export ANDROID_DATA /data
export ASEC_MOUNTPOINT /mnt/asec
export LOOP_MOUNTPOINT /mnt/obb
- export BOOTCLASSPATH /system/framework/core.jar:/system/framework/core-junit.jar:/system/framework/bouncycastle.jar:/system/framework/ext.jar:/system/framework/framework.jar:/system/framework/android.policy.jar:/system/framework/services.jar:/system/framework/apache-xml.jar
+ export BOOTCLASSPATH /system/framework/core.jar:/system/framework/core-junit.jar:/system/framework/bouncycastle.jar:/system/framework/ext.jar:/system/framework/framework.jar:/system/framework/telephony-common.jar:/system/framework/mms-common.jar:/system/framework/android.policy.jar:/system/framework/services.jar:/system/framework/apache-xml.jar
# Backward compatibility
symlink /system/etc /etc
@@ -169,7 +169,7 @@
# create basic filesystem structure
mkdir /data/misc 01771 system misc
- mkdir /data/misc/bluetoothd 0770 bluetooth bluetooth
+ mkdir /data/misc/bluedroid 0770 bluetooth bluetooth
mkdir /data/misc/bluetooth 0770 system system
mkdir /data/misc/keystore 0700 keystore keystore
mkdir /data/misc/keychain 0771 system system
@@ -393,7 +393,7 @@
socket rild stream 660 root radio
socket rild-debug stream 660 radio system
user root
- group radio cache inet misc audio sdcard_rw log
+ group radio cache inet misc audio sdcard_r sdcard_rw log
service surfaceflinger /system/bin/surfaceflinger
class main
@@ -427,21 +427,6 @@
disabled
oneshot
-service dbus /system/bin/dbus-daemon --system --nofork
- class main
- socket dbus stream 660 bluetooth bluetooth
- user bluetooth
- group bluetooth net_bt_admin
-
-service bluetoothd /system/bin/bluetoothd -n
- class main
- socket bluetooth stream 660 bluetooth bluetooth
- socket dbus_bluetooth stream 660 bluetooth bluetooth
- # init.rc does not yet support applying capabilities, so run as root and
- # let bluetoothd drop uid to bluetooth with the right linux capabilities
- group bluetooth net_bt_admin misc
- disabled
-
service installd /system/bin/installd
class main
socket installd stream 600 system system
diff --git a/toolbox/Android.mk b/toolbox/Android.mk
index be95e7c..086ba0d 100644
--- a/toolbox/Android.mk
+++ b/toolbox/Android.mk
@@ -56,6 +56,7 @@
ionice \
touch \
lsof \
+ du \
md5
ifeq ($(HAVE_SELINUX),true)
@@ -77,10 +78,17 @@
TOOLS += r
endif
-LOCAL_SRC_FILES:= \
+ALL_TOOLS = $(TOOLS)
+ALL_TOOLS += \
+ cp \
+ grep
+
+LOCAL_SRC_FILES := \
dynarray.c \
toolbox.c \
- $(patsubst %,%.c,$(TOOLS))
+ $(patsubst %,%.c,$(TOOLS)) \
+ cp/cp.c cp/utils.c \
+ grep/grep.c grep/fastgrep.c grep/file.c grep/queue.c grep/util.c
LOCAL_SHARED_LIBRARIES := libcutils libc libusbhost
@@ -94,7 +102,7 @@
endif
-LOCAL_MODULE:= toolbox
+LOCAL_MODULE := toolbox
# Including this will define $(intermediates).
#
@@ -103,7 +111,7 @@
$(LOCAL_PATH)/toolbox.c: $(intermediates)/tools.h
TOOLS_H := $(intermediates)/tools.h
-$(TOOLS_H): PRIVATE_TOOLS := $(TOOLS)
+$(TOOLS_H): PRIVATE_TOOLS := $(ALL_TOOLS)
$(TOOLS_H): PRIVATE_CUSTOM_TOOL = echo "/* file generated automatically */" > $@ ; for t in $(PRIVATE_TOOLS) ; do echo "TOOL($$t)" >> $@ ; done
$(TOOLS_H): $(LOCAL_PATH)/Android.mk
$(TOOLS_H):
@@ -111,7 +119,7 @@
# Make #!/system/bin/toolbox launchers for each tool.
#
-SYMLINKS := $(addprefix $(TARGET_OUT)/bin/,$(TOOLS))
+SYMLINKS := $(addprefix $(TARGET_OUT)/bin/,$(ALL_TOOLS))
$(SYMLINKS): TOOLBOX_BINARY := $(LOCAL_MODULE)
$(SYMLINKS): $(LOCAL_INSTALLED_MODULE) $(LOCAL_PATH)/Android.mk
@echo "Symlink: $@ -> $(TOOLBOX_BINARY)"
diff --git a/toolbox/cp/cp.c b/toolbox/cp/cp.c
new file mode 100644
index 0000000..bd3c70e
--- /dev/null
+++ b/toolbox/cp/cp.c
@@ -0,0 +1,552 @@
+/* $NetBSD: cp.c,v 1.58 2012/01/04 15:58:37 christos Exp $ */
+
+/*
+ * Copyright (c) 1988, 1993, 1994
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * David Hitz of Auspex Systems Inc.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#ifndef lint
+__COPYRIGHT(
+"@(#) Copyright (c) 1988, 1993, 1994\
+ The Regents of the University of California. All rights reserved.");
+#endif /* not lint */
+
+#ifndef lint
+#if 0
+static char sccsid[] = "@(#)cp.c 8.5 (Berkeley) 4/29/95";
+#else
+__RCSID("$NetBSD: cp.c,v 1.58 2012/01/04 15:58:37 christos Exp $");
+#endif
+#endif /* not lint */
+
+/*
+ * Cp copies source files to target files.
+ *
+ * The global PATH_T structure "to" always contains the path to the
+ * current target file. Since fts(3) does not change directories,
+ * this path can be either absolute or dot-relative.
+ *
+ * The basic algorithm is to initialize "to" and use fts(3) to traverse
+ * the file hierarchy rooted in the argument list. A trivial case is the
+ * case of 'cp file1 file2'. The more interesting case is the case of
+ * 'cp file1 file2 ... fileN dir' where the hierarchy is traversed and the
+ * path (relative to the root of the traversal) is appended to dir (stored
+ * in "to") to form the final target path.
+ */
+
+#include <sys/param.h>
+#include <sys/stat.h>
+
+#include <assert.h>
+#include <err.h>
+#include <errno.h>
+#include <fts.h>
+#include <locale.h>
+#include <signal.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "extern.h"
+
+#define STRIP_TRAILING_SLASH(p) { \
+ while ((p).p_end > (p).p_path + 1 && (p).p_end[-1] == '/') \
+ *--(p).p_end = '\0'; \
+}
+
+static char empty[] = "";
+PATH_T to = { .p_end = to.p_path, .target_end = empty };
+
+uid_t myuid;
+int Hflag, Lflag, Rflag, Pflag, fflag, iflag, lflag, pflag, rflag, vflag, Nflag;
+mode_t myumask;
+sig_atomic_t pinfo;
+
+enum op { FILE_TO_FILE, FILE_TO_DIR, DIR_TO_DNE };
+
+static int copy(char *[], enum op, int);
+
+static void
+progress(int sig __unused)
+{
+
+ pinfo++;
+}
+
+int
+cp_main(int argc, char *argv[])
+{
+ struct stat to_stat, tmp_stat;
+ enum op type;
+ int ch, fts_options, r, have_trailing_slash;
+ char *target, **src;
+
+#ifndef ANDROID
+ setprogname(argv[0]);
+#endif
+ (void)setlocale(LC_ALL, "");
+
+ Hflag = Lflag = Pflag = Rflag = 0;
+ while ((ch = getopt(argc, argv, "HLNPRfailprv")) != -1)
+ switch (ch) {
+ case 'H':
+ Hflag = 1;
+ Lflag = Pflag = 0;
+ break;
+ case 'L':
+ Lflag = 1;
+ Hflag = Pflag = 0;
+ break;
+ case 'N':
+ Nflag = 1;
+ break;
+ case 'P':
+ Pflag = 1;
+ Hflag = Lflag = 0;
+ break;
+ case 'R':
+ Rflag = 1;
+ break;
+ case 'a':
+ Pflag = 1;
+ pflag = 1;
+ Rflag = 1;
+ Hflag = Lflag = 0;
+ break;
+ case 'f':
+ fflag = 1;
+ iflag = 0;
+ break;
+ case 'i':
+ iflag = isatty(fileno(stdin));
+ fflag = 0;
+ break;
+ case 'l':
+ lflag = 1;
+ break;
+ case 'p':
+ pflag = 1;
+ break;
+ case 'r':
+ rflag = 1;
+ break;
+ case 'v':
+ vflag = 1;
+ break;
+ case '?':
+ default:
+ cp_usage();
+ /* NOTREACHED */
+ }
+ argc -= optind;
+ argv += optind;
+
+ if (argc < 2)
+ cp_usage();
+
+ fts_options = FTS_NOCHDIR | FTS_PHYSICAL;
+ if (rflag) {
+ if (Rflag) {
+ errx(EXIT_FAILURE,
+ "the -R and -r options may not be specified together.");
+ /* NOTREACHED */
+ }
+ if (Hflag || Lflag || Pflag) {
+ errx(EXIT_FAILURE,
+ "the -H, -L, and -P options may not be specified with the -r option.");
+ /* NOTREACHED */
+ }
+ fts_options &= ~FTS_PHYSICAL;
+ fts_options |= FTS_LOGICAL;
+ }
+
+ if (Rflag) {
+ if (Hflag)
+ fts_options |= FTS_COMFOLLOW;
+ if (Lflag) {
+ fts_options &= ~FTS_PHYSICAL;
+ fts_options |= FTS_LOGICAL;
+ }
+ } else if (!Pflag) {
+ fts_options &= ~FTS_PHYSICAL;
+ fts_options |= FTS_LOGICAL | FTS_COMFOLLOW;
+ }
+
+ myuid = getuid();
+
+ /* Copy the umask for explicit mode setting. */
+ myumask = umask(0);
+ (void)umask(myumask);
+
+ /* Save the target base in "to". */
+ target = argv[--argc];
+ if (strlcpy(to.p_path, target, sizeof(to.p_path)) >= sizeof(to.p_path))
+ errx(EXIT_FAILURE, "%s: name too long", target);
+ to.p_end = to.p_path + strlen(to.p_path);
+ have_trailing_slash = (to.p_end[-1] == '/');
+ if (have_trailing_slash)
+ STRIP_TRAILING_SLASH(to);
+ to.target_end = to.p_end;
+
+ /* Set end of argument list for fts(3). */
+ argv[argc] = NULL;
+
+#ifndef ANDROID
+ (void)signal(SIGINFO, progress);
+#endif
+
+ /*
+ * Cp has two distinct cases:
+ *
+ * cp [-R] source target
+ * cp [-R] source1 ... sourceN directory
+ *
+ * In both cases, source can be either a file or a directory.
+ *
+ * In (1), the target becomes a copy of the source. That is, if the
+ * source is a file, the target will be a file, and likewise for
+ * directories.
+ *
+ * In (2), the real target is not directory, but "directory/source".
+ */
+ if (Pflag)
+ r = lstat(to.p_path, &to_stat);
+ else
+ r = stat(to.p_path, &to_stat);
+ if (r == -1 && errno != ENOENT) {
+ err(EXIT_FAILURE, "%s", to.p_path);
+ /* NOTREACHED */
+ }
+ if (r == -1 || !S_ISDIR(to_stat.st_mode)) {
+ /*
+ * Case (1). Target is not a directory.
+ */
+ if (argc > 1)
+ cp_usage();
+ /*
+ * Need to detect the case:
+ * cp -R dir foo
+ * Where dir is a directory and foo does not exist, where
+ * we want pathname concatenations turned on but not for
+ * the initial mkdir().
+ */
+ if (r == -1) {
+ if (rflag || (Rflag && (Lflag || Hflag)))
+ r = stat(*argv, &tmp_stat);
+ else
+ r = lstat(*argv, &tmp_stat);
+ if (r == -1) {
+ err(EXIT_FAILURE, "%s", *argv);
+ /* NOTREACHED */
+ }
+
+ if (S_ISDIR(tmp_stat.st_mode) && (Rflag || rflag))
+ type = DIR_TO_DNE;
+ else
+ type = FILE_TO_FILE;
+ } else
+ type = FILE_TO_FILE;
+
+ if (have_trailing_slash && type == FILE_TO_FILE) {
+ if (r == -1)
+ errx(1, "directory %s does not exist",
+ to.p_path);
+ else
+ errx(1, "%s is not a directory", to.p_path);
+ }
+ } else {
+ /*
+ * Case (2). Target is a directory.
+ */
+ type = FILE_TO_DIR;
+ }
+
+ /*
+ * make "cp -rp src/ dst" behave like "cp -rp src dst" not
+ * like "cp -rp src/. dst"
+ */
+ for (src = argv; *src; src++) {
+ size_t len = strlen(*src);
+ while (len-- > 1 && (*src)[len] == '/')
+ (*src)[len] = '\0';
+ }
+
+ exit(copy(argv, type, fts_options));
+ /* NOTREACHED */
+}
+
+static int dnestack[MAXPATHLEN]; /* unlikely we'll have more nested dirs */
+static ssize_t dnesp;
+static void
+pushdne(int dne)
+{
+
+ dnestack[dnesp++] = dne;
+ assert(dnesp < MAXPATHLEN);
+}
+
+static int
+popdne(void)
+{
+ int rv;
+
+ rv = dnestack[--dnesp];
+ assert(dnesp >= 0);
+ return rv;
+}
+
+static int
+copy(char *argv[], enum op type, int fts_options)
+{
+ struct stat to_stat;
+ FTS *ftsp;
+ FTSENT *curr;
+ int base, dne, sval;
+ int this_failed, any_failed;
+ size_t nlen;
+ char *p, *target_mid;
+
+ base = 0; /* XXX gcc -Wuninitialized (see comment below) */
+
+ if ((ftsp = fts_open(argv, fts_options, NULL)) == NULL)
+ err(EXIT_FAILURE, "%s", argv[0]);
+ /* NOTREACHED */
+ for (any_failed = 0; (curr = fts_read(ftsp)) != NULL;) {
+ this_failed = 0;
+ switch (curr->fts_info) {
+ case FTS_NS:
+ case FTS_DNR:
+ case FTS_ERR:
+ warnx("%s: %s", curr->fts_path,
+ strerror(curr->fts_errno));
+ this_failed = any_failed = 1;
+ continue;
+ case FTS_DC: /* Warn, continue. */
+ warnx("%s: directory causes a cycle", curr->fts_path);
+ this_failed = any_failed = 1;
+ continue;
+ }
+
+ /*
+ * If we are in case (2) or (3) above, we need to append the
+ * source name to the target name.
+ */
+ if (type != FILE_TO_FILE) {
+ if ((curr->fts_namelen +
+ to.target_end - to.p_path + 1) > MAXPATHLEN) {
+ warnx("%s/%s: name too long (not copied)",
+ to.p_path, curr->fts_name);
+ this_failed = any_failed = 1;
+ continue;
+ }
+
+ /*
+ * Need to remember the roots of traversals to create
+ * correct pathnames. If there's a directory being
+ * copied to a non-existent directory, e.g.
+ * cp -R a/dir noexist
+ * the resulting path name should be noexist/foo, not
+ * noexist/dir/foo (where foo is a file in dir), which
+ * is the case where the target exists.
+ *
+ * Also, check for "..". This is for correct path
+ * concatentation for paths ending in "..", e.g.
+ * cp -R .. /tmp
+ * Paths ending in ".." are changed to ".". This is
+ * tricky, but seems the easiest way to fix the problem.
+ *
+ * XXX
+ * Since the first level MUST be FTS_ROOTLEVEL, base
+ * is always initialized.
+ */
+ if (curr->fts_level == FTS_ROOTLEVEL) {
+ if (type != DIR_TO_DNE) {
+ p = strrchr(curr->fts_path, '/');
+ base = (p == NULL) ? 0 :
+ (int)(p - curr->fts_path + 1);
+
+ if (!strcmp(&curr->fts_path[base],
+ ".."))
+ base += 1;
+ } else
+ base = curr->fts_pathlen;
+ }
+
+ p = &curr->fts_path[base];
+ nlen = curr->fts_pathlen - base;
+ target_mid = to.target_end;
+ if (*p != '/' && target_mid[-1] != '/')
+ *target_mid++ = '/';
+ *target_mid = 0;
+
+ if (target_mid - to.p_path + nlen >= PATH_MAX) {
+ warnx("%s%s: name too long (not copied)",
+ to.p_path, p);
+ this_failed = any_failed = 1;
+ continue;
+ }
+ (void)strncat(target_mid, p, nlen);
+ to.p_end = target_mid + nlen;
+ *to.p_end = 0;
+ STRIP_TRAILING_SLASH(to);
+ }
+
+ sval = Pflag ? lstat(to.p_path, &to_stat) : stat(to.p_path, &to_stat);
+ /* Not an error but need to remember it happened */
+ if (sval == -1)
+ dne = 1;
+ else {
+ if (to_stat.st_dev == curr->fts_statp->st_dev &&
+ to_stat.st_ino == curr->fts_statp->st_ino) {
+ warnx("%s and %s are identical (not copied).",
+ to.p_path, curr->fts_path);
+ this_failed = any_failed = 1;
+ if (S_ISDIR(curr->fts_statp->st_mode))
+ (void)fts_set(ftsp, curr, FTS_SKIP);
+ continue;
+ }
+ if (!S_ISDIR(curr->fts_statp->st_mode) &&
+ S_ISDIR(to_stat.st_mode)) {
+ warnx("cannot overwrite directory %s with non-directory %s",
+ to.p_path, curr->fts_path);
+ this_failed = any_failed = 1;
+ continue;
+ }
+ dne = 0;
+ }
+
+ switch (curr->fts_statp->st_mode & S_IFMT) {
+ case S_IFLNK:
+ /* Catch special case of a non dangling symlink */
+ if((fts_options & FTS_LOGICAL) ||
+ ((fts_options & FTS_COMFOLLOW) && curr->fts_level == 0)) {
+ if (copy_file(curr, dne))
+ this_failed = any_failed = 1;
+ } else {
+ if (copy_link(curr, !dne))
+ this_failed = any_failed = 1;
+ }
+ break;
+ case S_IFDIR:
+ if (!Rflag && !rflag) {
+ if (curr->fts_info == FTS_D)
+ warnx("%s is a directory (not copied).",
+ curr->fts_path);
+ (void)fts_set(ftsp, curr, FTS_SKIP);
+ this_failed = any_failed = 1;
+ break;
+ }
+
+ /*
+ * Directories get noticed twice:
+ * In the first pass, create it if needed.
+ * In the second pass, after the children have been copied, set the permissions.
+ */
+ if (curr->fts_info == FTS_D) /* First pass */
+ {
+ /*
+ * If the directory doesn't exist, create the new
+ * one with the from file mode plus owner RWX bits,
+ * modified by the umask. Trade-off between being
+ * able to write the directory (if from directory is
+ * 555) and not causing a permissions race. If the
+ * umask blocks owner writes, we fail..
+ */
+ pushdne(dne);
+ if (dne) {
+ if (mkdir(to.p_path,
+ curr->fts_statp->st_mode | S_IRWXU) < 0)
+ err(EXIT_FAILURE, "%s",
+ to.p_path);
+ /* NOTREACHED */
+ } else if (!S_ISDIR(to_stat.st_mode)) {
+ errno = ENOTDIR;
+ err(EXIT_FAILURE, "%s",
+ to.p_path);
+ /* NOTREACHED */
+ }
+ }
+ else if (curr->fts_info == FTS_DP) /* Second pass */
+ {
+ /*
+ * If not -p and directory didn't exist, set it to be
+ * the same as the from directory, umodified by the
+ * umask; arguably wrong, but it's been that way
+ * forever.
+ */
+ if (pflag && setfile(curr->fts_statp, 0))
+ this_failed = any_failed = 1;
+ else if ((dne = popdne()))
+ (void)chmod(to.p_path,
+ curr->fts_statp->st_mode);
+ }
+ else
+ {
+ warnx("directory %s encountered when not expected.",
+ curr->fts_path);
+ this_failed = any_failed = 1;
+ break;
+ }
+
+ break;
+ case S_IFBLK:
+ case S_IFCHR:
+ if (Rflag) {
+ if (copy_special(curr->fts_statp, !dne))
+ this_failed = any_failed = 1;
+ } else
+ if (copy_file(curr, dne))
+ this_failed = any_failed = 1;
+ break;
+ case S_IFIFO:
+ if (Rflag) {
+ if (copy_fifo(curr->fts_statp, !dne))
+ this_failed = any_failed = 1;
+ } else
+ if (copy_file(curr, dne))
+ this_failed = any_failed = 1;
+ break;
+ default:
+ if (copy_file(curr, dne))
+ this_failed = any_failed = 1;
+ break;
+ }
+ if (vflag && !this_failed)
+ (void)printf("%s -> %s\n", curr->fts_path, to.p_path);
+ }
+ if (errno) {
+ err(EXIT_FAILURE, "fts_read");
+ /* NOTREACHED */
+ }
+ (void)fts_close(ftsp);
+ return (any_failed);
+}
diff --git a/toolbox/cp/extern.h b/toolbox/cp/extern.h
new file mode 100644
index 0000000..ffbadf7
--- /dev/null
+++ b/toolbox/cp/extern.h
@@ -0,0 +1,61 @@
+/* $NetBSD: extern.h,v 1.17 2012/01/04 15:58:37 christos Exp $ */
+
+/*-
+ * Copyright (c) 1991, 1993, 1994
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ * @(#)extern.h 8.2 (Berkeley) 4/1/94
+ */
+
+#ifndef _EXTERN_H_
+#define _EXTERN_H_
+
+typedef struct {
+ char *p_end; /* pointer to NULL at end of path */
+ char *target_end; /* pointer to end of target base */
+ char p_path[MAXPATHLEN + 1]; /* pointer to the start of a path */
+} PATH_T;
+
+extern PATH_T to;
+extern uid_t myuid;
+extern int Rflag, rflag, Hflag, Lflag, Pflag, fflag, iflag, lflag, pflag, Nflag;
+extern mode_t myumask;
+extern sig_atomic_t pinfo;
+
+#include <sys/cdefs.h>
+
+__BEGIN_DECLS
+int copy_fifo(struct stat *, int);
+int copy_file(FTSENT *, int);
+int copy_link(FTSENT *, int);
+int copy_special(struct stat *, int);
+int set_utimes(const char *, struct stat *);
+int setfile(struct stat *, int);
+void cp_usage(void) __attribute__((__noreturn__));
+__END_DECLS
+
+#endif /* !_EXTERN_H_ */
diff --git a/toolbox/cp/utils.c b/toolbox/cp/utils.c
new file mode 100644
index 0000000..b682bbe
--- /dev/null
+++ b/toolbox/cp/utils.c
@@ -0,0 +1,446 @@
+/* $NetBSD: utils.c,v 1.41 2012/01/04 15:58:37 christos Exp $ */
+
+/*-
+ * Copyright (c) 1991, 1993, 1994
+ * The Regents of the University of California. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#ifndef lint
+#if 0
+static char sccsid[] = "@(#)utils.c 8.3 (Berkeley) 4/1/94";
+#else
+__RCSID("$NetBSD: utils.c,v 1.41 2012/01/04 15:58:37 christos Exp $");
+#endif
+#endif /* not lint */
+
+#include <sys/mman.h>
+#include <sys/param.h>
+#include <sys/stat.h>
+#include <sys/time.h>
+#ifndef ANDROID
+#include <sys/extattr.h>
+#endif
+
+#include <err.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <fts.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "extern.h"
+
+#ifdef ANDROID
+#define MAXBSIZE 65536
+#endif
+
+#define MMAP_MAX_SIZE (8 * 1048576)
+#define MMAP_MAX_WRITE (64 * 1024)
+
+int
+set_utimes(const char *file, struct stat *fs)
+{
+ static struct timeval tv[2];
+
+#ifdef ANDROID
+ tv[0].tv_sec = fs->st_atime;
+ tv[0].tv_usec = 0;
+ tv[1].tv_sec = fs->st_mtime;
+ tv[1].tv_usec = 0;
+
+ if (utimes(file, tv)) {
+ warn("utimes: %s", file);
+ return 1;
+ }
+#else
+ TIMESPEC_TO_TIMEVAL(&tv[0], &fs->st_atimespec);
+ TIMESPEC_TO_TIMEVAL(&tv[1], &fs->st_mtimespec);
+
+ if (lutimes(file, tv)) {
+ warn("lutimes: %s", file);
+ return (1);
+ }
+#endif
+ return (0);
+}
+
+struct finfo {
+ const char *from;
+ const char *to;
+ size_t size;
+};
+
+static void
+progress(const struct finfo *fi, size_t written)
+{
+ int pcent = (int)((100.0 * written) / fi->size);
+
+ pinfo = 0;
+ (void)fprintf(stderr, "%s => %s %zu/%zu bytes %d%% written\n",
+ fi->from, fi->to, written, fi->size, pcent);
+}
+
+int
+copy_file(FTSENT *entp, int dne)
+{
+ static char buf[MAXBSIZE];
+ struct stat to_stat, *fs;
+ int ch, checkch, from_fd, rcount, rval, to_fd, tolnk, wcount;
+ char *p;
+ size_t ptotal = 0;
+
+ if ((from_fd = open(entp->fts_path, O_RDONLY, 0)) == -1) {
+ warn("%s", entp->fts_path);
+ return (1);
+ }
+
+ to_fd = -1;
+ fs = entp->fts_statp;
+ tolnk = ((Rflag && !(Lflag || Hflag)) || Pflag);
+
+ /*
+ * If the file exists and we're interactive, verify with the user.
+ * If the file DNE, set the mode to be the from file, minus setuid
+ * bits, modified by the umask; arguably wrong, but it makes copying
+ * executables work right and it's been that way forever. (The
+ * other choice is 666 or'ed with the execute bits on the from file
+ * modified by the umask.)
+ */
+ if (!dne) {
+ struct stat sb;
+ int sval;
+
+ if (iflag) {
+ (void)fprintf(stderr, "overwrite %s? ", to.p_path);
+ checkch = ch = getchar();
+ while (ch != '\n' && ch != EOF)
+ ch = getchar();
+ if (checkch != 'y' && checkch != 'Y') {
+ (void)close(from_fd);
+ return (0);
+ }
+ }
+
+ sval = tolnk ?
+ lstat(to.p_path, &sb) : stat(to.p_path, &sb);
+ if (sval == -1) {
+ warn("stat: %s", to.p_path);
+ (void)close(from_fd);
+ return (1);
+ }
+
+ if (!(tolnk && S_ISLNK(sb.st_mode)))
+ to_fd = open(to.p_path, O_WRONLY | O_TRUNC, 0);
+ } else
+ to_fd = open(to.p_path, O_WRONLY | O_TRUNC | O_CREAT,
+ fs->st_mode & ~(S_ISUID | S_ISGID));
+
+ if (to_fd == -1 && (fflag || tolnk)) {
+ /*
+ * attempt to remove existing destination file name and
+ * create a new file
+ */
+ (void)unlink(to.p_path);
+ to_fd = open(to.p_path, O_WRONLY | O_TRUNC | O_CREAT,
+ fs->st_mode & ~(S_ISUID | S_ISGID));
+ }
+
+ if (to_fd == -1) {
+ warn("%s", to.p_path);
+ (void)close(from_fd);
+ return (1);
+ }
+
+ rval = 0;
+
+ /* if hard linking then simply close the open fds, link and return */
+ if (lflag) {
+ (void)close(from_fd);
+ (void)close(to_fd);
+ (void)unlink(to.p_path);
+ if (link(entp->fts_path, to.p_path)) {
+ warn("%s", to.p_path);
+ return (1);
+ }
+ return (0);
+ }
+ /* NOTREACHED */
+
+ /*
+ * There's no reason to do anything other than close the file
+ * now if it's empty, so let's not bother.
+ */
+ if (fs->st_size > 0) {
+ struct finfo fi;
+
+ fi.from = entp->fts_path;
+ fi.to = to.p_path;
+ fi.size = (size_t)fs->st_size;
+
+ /*
+ * Mmap and write if less than 8M (the limit is so
+ * we don't totally trash memory on big files).
+ * This is really a minor hack, but it wins some CPU back.
+ */
+ bool use_read;
+
+ use_read = true;
+ if (fs->st_size <= MMAP_MAX_SIZE) {
+ size_t fsize = (size_t)fs->st_size;
+ p = mmap(NULL, fsize, PROT_READ, MAP_FILE|MAP_SHARED,
+ from_fd, (off_t)0);
+ if (p != MAP_FAILED) {
+ size_t remainder;
+
+ use_read = false;
+
+ (void) madvise(p, (size_t)fs->st_size,
+ MADV_SEQUENTIAL);
+
+ /*
+ * Write out the data in small chunks to
+ * avoid locking the output file for a
+ * long time if the reading the data from
+ * the source is slow.
+ */
+ remainder = fsize;
+ do {
+ ssize_t chunk;
+
+ chunk = (remainder > MMAP_MAX_WRITE) ?
+ MMAP_MAX_WRITE : remainder;
+ if (write(to_fd, &p[fsize - remainder],
+ chunk) != chunk) {
+ warn("%s", to.p_path);
+ rval = 1;
+ break;
+ }
+ remainder -= chunk;
+ ptotal += chunk;
+ if (pinfo)
+ progress(&fi, ptotal);
+ } while (remainder > 0);
+
+ if (munmap(p, fsize) < 0) {
+ warn("%s", entp->fts_path);
+ rval = 1;
+ }
+ }
+ }
+
+ if (use_read) {
+ while ((rcount = read(from_fd, buf, MAXBSIZE)) > 0) {
+ wcount = write(to_fd, buf, (size_t)rcount);
+ if (rcount != wcount || wcount == -1) {
+ warn("%s", to.p_path);
+ rval = 1;
+ break;
+ }
+ ptotal += wcount;
+ if (pinfo)
+ progress(&fi, ptotal);
+ }
+ if (rcount < 0) {
+ warn("%s", entp->fts_path);
+ rval = 1;
+ }
+ }
+ }
+
+#ifndef ANDROID
+ if (pflag && (fcpxattr(from_fd, to_fd) != 0))
+ warn("%s: error copying extended attributes", to.p_path);
+#endif
+
+ (void)close(from_fd);
+
+ if (rval == 1) {
+ (void)close(to_fd);
+ return (1);
+ }
+
+ if (pflag && setfile(fs, to_fd))
+ rval = 1;
+ /*
+ * If the source was setuid or setgid, lose the bits unless the
+ * copy is owned by the same user and group.
+ */
+#define RETAINBITS \
+ (S_ISUID | S_ISGID | S_ISVTX | S_IRWXU | S_IRWXG | S_IRWXO)
+ if (!pflag && dne
+ && fs->st_mode & (S_ISUID | S_ISGID) && fs->st_uid == myuid) {
+ if (fstat(to_fd, &to_stat)) {
+ warn("%s", to.p_path);
+ rval = 1;
+ } else if (fs->st_gid == to_stat.st_gid &&
+ fchmod(to_fd, fs->st_mode & RETAINBITS & ~myumask)) {
+ warn("%s", to.p_path);
+ rval = 1;
+ }
+ }
+ if (close(to_fd)) {
+ warn("%s", to.p_path);
+ rval = 1;
+ }
+ /* set the mod/access times now after close of the fd */
+ if (pflag && set_utimes(to.p_path, fs)) {
+ rval = 1;
+ }
+ return (rval);
+}
+
+int
+copy_link(FTSENT *p, int exists)
+{
+ int len;
+ char target[MAXPATHLEN];
+
+ if ((len = readlink(p->fts_path, target, sizeof(target)-1)) == -1) {
+ warn("readlink: %s", p->fts_path);
+ return (1);
+ }
+ target[len] = '\0';
+ if (exists && unlink(to.p_path)) {
+ warn("unlink: %s", to.p_path);
+ return (1);
+ }
+ if (symlink(target, to.p_path)) {
+ warn("symlink: %s", target);
+ return (1);
+ }
+ return (pflag ? setfile(p->fts_statp, 0) : 0);
+}
+
+int
+copy_fifo(struct stat *from_stat, int exists)
+{
+ if (exists && unlink(to.p_path)) {
+ warn("unlink: %s", to.p_path);
+ return (1);
+ }
+ if (mkfifo(to.p_path, from_stat->st_mode)) {
+ warn("mkfifo: %s", to.p_path);
+ return (1);
+ }
+ return (pflag ? setfile(from_stat, 0) : 0);
+}
+
+int
+copy_special(struct stat *from_stat, int exists)
+{
+ if (exists && unlink(to.p_path)) {
+ warn("unlink: %s", to.p_path);
+ return (1);
+ }
+ if (mknod(to.p_path, from_stat->st_mode, from_stat->st_rdev)) {
+ warn("mknod: %s", to.p_path);
+ return (1);
+ }
+ return (pflag ? setfile(from_stat, 0) : 0);
+}
+
+
+/*
+ * Function: setfile
+ *
+ * Purpose:
+ * Set the owner/group/permissions for the "to" file to the information
+ * in the stat structure. If fd is zero, also call set_utimes() to set
+ * the mod/access times. If fd is non-zero, the caller must do a utimes
+ * itself after close(fd).
+ */
+int
+setfile(struct stat *fs, int fd)
+{
+ int rval, islink;
+
+ rval = 0;
+ islink = S_ISLNK(fs->st_mode);
+ fs->st_mode &= S_ISUID | S_ISGID | S_IRWXU | S_IRWXG | S_IRWXO;
+
+ /*
+ * Changing the ownership probably won't succeed, unless we're root
+ * or POSIX_CHOWN_RESTRICTED is not set. Set uid/gid before setting
+ * the mode; current BSD behavior is to remove all setuid bits on
+ * chown. If chown fails, lose setuid/setgid bits.
+ */
+ if (fd ? fchown(fd, fs->st_uid, fs->st_gid) :
+ lchown(to.p_path, fs->st_uid, fs->st_gid)) {
+ if (errno != EPERM) {
+ warn("chown: %s", to.p_path);
+ rval = 1;
+ }
+ fs->st_mode &= ~(S_ISUID | S_ISGID);
+ }
+#ifdef ANDROID
+ if (fd ? fchmod(fd, fs->st_mode) : chmod(to.p_path, fs->st_mode)) {
+#else
+ if (fd ? fchmod(fd, fs->st_mode) : lchmod(to.p_path, fs->st_mode)) {
+#endif
+ warn("chmod: %s", to.p_path);
+ rval = 1;
+ }
+
+#ifndef ANDROID
+ if (!islink && !Nflag) {
+ unsigned long fflags = fs->st_flags;
+ /*
+ * XXX
+ * NFS doesn't support chflags; ignore errors unless
+ * there's reason to believe we're losing bits.
+ * (Note, this still won't be right if the server
+ * supports flags and we were trying to *remove* flags
+ * on a file that we copied, i.e., that we didn't create.)
+ */
+ errno = 0;
+ if ((fd ? fchflags(fd, fflags) :
+ chflags(to.p_path, fflags)) == -1)
+ if (errno != EOPNOTSUPP || fs->st_flags != 0) {
+ warn("chflags: %s", to.p_path);
+ rval = 1;
+ }
+ }
+#endif
+ /* if fd is non-zero, caller must call set_utimes() after close() */
+ if (fd == 0 && set_utimes(to.p_path, fs))
+ rval = 1;
+ return (rval);
+}
+
+void
+cp_usage(void)
+{
+ (void)fprintf(stderr,
+ "usage: cp [-R [-H | -L | -P]] [-f | -i] [-alNpv] src target\n"
+ " cp [-R [-H | -L | -P]] [-f | -i] [-alNpv] src1 ... srcN directory\n");
+ exit(1);
+ /* NOTREACHED */
+}
diff --git a/toolbox/du.c b/toolbox/du.c
new file mode 100644
index 0000000..06374a4
--- /dev/null
+++ b/toolbox/du.c
@@ -0,0 +1,322 @@
+/* $NetBSD: du.c,v 1.33 2008/07/30 22:03:40 dsl Exp $ */
+
+/*
+ * Copyright (c) 1989, 1993, 1994
+ * The Regents of the University of California. All rights reserved.
+ *
+ * This code is derived from software contributed to Berkeley by
+ * Chris Newcomb.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the University nor the names of its contributors
+ * may be used to endorse or promote products derived from this software
+ * without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#include <sys/cdefs.h>
+#ifndef lint
+__COPYRIGHT("@(#) Copyright (c) 1989, 1993, 1994\
+ The Regents of the University of California. All rights reserved.");
+#endif /* not lint */
+
+#ifndef lint
+#if 0
+static char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95";
+#else
+__RCSID("$NetBSD: du.c,v 1.33 2008/07/30 22:03:40 dsl Exp $");
+#endif
+#endif /* not lint */
+
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#include <dirent.h>
+#include <err.h>
+#include <errno.h>
+#include <fts.h>
+#include <util.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <limits.h>
+
+int linkchk(dev_t, ino_t);
+void prstat(const char *, int64_t);
+void usage(void);
+
+long blocksize;
+
+#define howmany(x, y) (((x)+((y)-1))/(y))
+
+int
+du_main(int argc, char *argv[])
+{
+ FTS *fts;
+ FTSENT *p;
+ int64_t totalblocks;
+ int ftsoptions, listfiles;
+ int depth;
+ int Hflag, Lflag, aflag, ch, cflag, dflag, gkmflag, nflag, rval, sflag;
+ const char *noargv[2];
+
+ Hflag = Lflag = aflag = cflag = dflag = gkmflag = sflag = 0;
+ totalblocks = 0;
+ ftsoptions = FTS_PHYSICAL;
+ depth = INT_MAX;
+ while ((ch = getopt(argc, argv, "HLPacd:ghkmnrsx")) != -1)
+ switch (ch) {
+ case 'H':
+ Hflag = 1;
+ Lflag = 0;
+ break;
+ case 'L':
+ Lflag = 1;
+ Hflag = 0;
+ break;
+ case 'P':
+ Hflag = Lflag = 0;
+ break;
+ case 'a':
+ aflag = 1;
+ break;
+ case 'c':
+ cflag = 1;
+ break;
+ case 'd':
+ dflag = 1;
+ depth = atoi(optarg);
+ if (depth < 0 || depth > SHRT_MAX) {
+ warnx("invalid argument to option d: %s",
+ optarg);
+ usage();
+ }
+ break;
+ case 'g':
+ blocksize = 1024 * 1024 * 1024;
+ gkmflag = 1;
+ break;
+ case 'k':
+ blocksize = 1024;
+ gkmflag = 1;
+ break;
+ case 'm':
+ blocksize = 1024 * 1024;
+ gkmflag = 1;
+ break;
+ case 'r':
+ break;
+ case 's':
+ sflag = 1;
+ break;
+ case 'x':
+ ftsoptions |= FTS_XDEV;
+ break;
+ case '?':
+ default:
+ usage();
+ }
+ argc -= optind;
+ argv += optind;
+
+ /*
+ * XXX
+ * Because of the way that fts(3) works, logical walks will not count
+ * the blocks actually used by symbolic links. We rationalize this by
+ * noting that users computing logical sizes are likely to do logical
+ * copies, so not counting the links is correct. The real reason is
+ * that we'd have to re-implement the kernel's symbolic link traversing
+ * algorithm to get this right. If, for example, you have relative
+ * symbolic links referencing other relative symbolic links, it gets
+ * very nasty, very fast. The bottom line is that it's documented in
+ * the man page, so it's a feature.
+ */
+ if (Hflag)
+ ftsoptions |= FTS_COMFOLLOW;
+ if (Lflag) {
+ ftsoptions &= ~FTS_PHYSICAL;
+ ftsoptions |= FTS_LOGICAL;
+ }
+
+ listfiles = 0;
+ if (aflag) {
+ if (sflag || dflag)
+ usage();
+ listfiles = 1;
+ } else if (sflag) {
+ if (dflag)
+ usage();
+ depth = 0;
+ }
+
+ if (!*argv) {
+ noargv[0] = ".";
+ noargv[1] = NULL;
+ argv = __UNCONST(noargv);
+ }
+
+ if (!gkmflag)
+ blocksize = 512;
+ blocksize /= 512;
+
+ if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
+ err(1, "fts_open `%s'", *argv);
+
+ for (rval = 0; (p = fts_read(fts)) != NULL;) {
+ switch (p->fts_info) {
+ case FTS_D: /* Ignore. */
+ break;
+ case FTS_DP:
+ p->fts_parent->fts_number +=
+ p->fts_number += p->fts_statp->st_blocks;
+ if (cflag)
+ totalblocks += p->fts_statp->st_blocks;
+ /*
+ * If listing each directory, or not listing files
+ * or directories and this is post-order of the
+ * root of a traversal, display the total.
+ */
+ if (p->fts_level <= depth
+ || (!listfiles && !p->fts_level))
+ prstat(p->fts_path, p->fts_number);
+ break;
+ case FTS_DC: /* Ignore. */
+ break;
+ case FTS_DNR: /* Warn, continue. */
+ case FTS_ERR:
+ case FTS_NS:
+ warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
+ rval = 1;
+ break;
+ default:
+ if (p->fts_statp->st_nlink > 1 &&
+ linkchk(p->fts_statp->st_dev, p->fts_statp->st_ino))
+ break;
+ /*
+ * If listing each file, or a non-directory file was
+ * the root of a traversal, display the total.
+ */
+ if (listfiles || !p->fts_level)
+ prstat(p->fts_path, p->fts_statp->st_blocks);
+ p->fts_parent->fts_number += p->fts_statp->st_blocks;
+ if (cflag)
+ totalblocks += p->fts_statp->st_blocks;
+ }
+ }
+ if (errno)
+ err(1, "fts_read");
+ if (cflag)
+ prstat("total", totalblocks);
+ exit(rval);
+}
+
+void
+prstat(const char *fname, int64_t blocks)
+{
+ (void)printf("%lld\t%s\n",
+ (long long)howmany(blocks, (int64_t)blocksize),
+ fname);
+}
+
+int
+linkchk(dev_t dev, ino_t ino)
+{
+ static struct entry {
+ dev_t dev;
+ ino_t ino;
+ } *htable;
+ static int htshift; /* log(allocated size) */
+ static int htmask; /* allocated size - 1 */
+ static int htused; /* 2*number of insertions */
+ static int sawzero; /* Whether zero is in table or not */
+ int h, h2;
+ uint64_t tmp;
+ /* this constant is (1<<64)/((1+sqrt(5))/2)
+ * aka (word size)/(golden ratio)
+ */
+ const uint64_t HTCONST = 11400714819323198485ULL;
+ const int HTBITS = CHAR_BIT * sizeof(tmp);
+
+ /* Never store zero in hashtable */
+ if (dev == 0 && ino == 0) {
+ h = sawzero;
+ sawzero = 1;
+ return h;
+ }
+
+ /* Extend hash table if necessary, keep load under 0.5 */
+ if (htused<<1 >= htmask) {
+ struct entry *ohtable;
+
+ if (!htable)
+ htshift = 10; /* starting hashtable size */
+ else
+ htshift++; /* exponential hashtable growth */
+
+ htmask = (1 << htshift) - 1;
+ htused = 0;
+
+ ohtable = htable;
+ htable = calloc(htmask+1, sizeof(*htable));
+ if (!htable)
+ err(1, "calloc");
+
+ /* populate newly allocated hashtable */
+ if (ohtable) {
+ int i;
+ for (i = 0; i <= htmask>>1; i++)
+ if (ohtable[i].ino || ohtable[i].dev)
+ linkchk(ohtable[i].dev, ohtable[i].ino);
+ free(ohtable);
+ }
+ }
+
+ /* multiplicative hashing */
+ tmp = dev;
+ tmp <<= HTBITS>>1;
+ tmp |= ino;
+ tmp *= HTCONST;
+ h = tmp >> (HTBITS - htshift);
+ h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
+
+ /* open address hashtable search with double hash probing */
+ while (htable[h].ino || htable[h].dev) {
+ if ((htable[h].ino == ino) && (htable[h].dev == dev))
+ return 1;
+ h = (h + h2) & htmask;
+ }
+
+ /* Insert the current entry into hashtable */
+ htable[h].dev = dev;
+ htable[h].ino = ino;
+ htused++;
+ return 0;
+}
+
+void
+usage(void)
+{
+
+ (void)fprintf(stderr,
+ "usage: du [-H | -L | -P] [-a | -d depth | -s] [-cgkmrx] [file ...]\n");
+ exit(1);
+}
diff --git a/toolbox/grep/fastgrep.c b/toolbox/grep/fastgrep.c
new file mode 100644
index 0000000..2fcd864
--- /dev/null
+++ b/toolbox/grep/fastgrep.c
@@ -0,0 +1,336 @@
+/* $OpenBSD: util.c,v 1.36 2007/10/02 17:59:18 otto Exp $ */
+/* $FreeBSD: head/usr.bin/grep/fastgrep.c 211496 2010-08-19 09:28:59Z des $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * XXX: This file is a speed up for grep to cover the defects of the
+ * regex library. These optimizations should practically be implemented
+ * there keeping this code clean. This is a future TODO, but for the
+ * meantime, we need to use this workaround.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: fastgrep.c,v 1.5 2011/04/18 03:27:40 joerg Exp $");
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "grep.h"
+
+static inline int grep_cmp(const unsigned char *, const unsigned char *, size_t);
+static inline void grep_revstr(unsigned char *, int);
+
+void
+fgrepcomp(fastgrep_t *fg, const char *pat)
+{
+ unsigned int i;
+
+ /* Initialize. */
+ fg->len = strlen(pat);
+ fg->bol = false;
+ fg->eol = false;
+ fg->reversed = false;
+
+ fg->pattern = (unsigned char *)grep_strdup(pat);
+
+ /* Preprocess pattern. */
+ for (i = 0; i <= UCHAR_MAX; i++)
+ fg->qsBc[i] = fg->len;
+ for (i = 1; i < fg->len; i++)
+ fg->qsBc[fg->pattern[i]] = fg->len - i;
+}
+
+/*
+ * Returns: -1 on failure, 0 on success
+ */
+int
+fastcomp(fastgrep_t *fg, const char *pat)
+{
+ unsigned int i;
+ int firstHalfDot = -1;
+ int firstLastHalfDot = -1;
+ int hasDot = 0;
+ int lastHalfDot = 0;
+ int shiftPatternLen;
+
+ /* Initialize. */
+ fg->len = strlen(pat);
+ fg->bol = false;
+ fg->eol = false;
+ fg->reversed = false;
+ fg->word = wflag;
+
+ /* Remove end-of-line character ('$'). */
+ if (fg->len > 0 && pat[fg->len - 1] == '$') {
+ fg->eol = true;
+ fg->len--;
+ }
+
+ /* Remove beginning-of-line character ('^'). */
+ if (pat[0] == '^') {
+ fg->bol = true;
+ fg->len--;
+ pat++;
+ }
+
+ if (fg->len >= 14 &&
+ memcmp(pat, "[[:<:]]", 7) == 0 &&
+ memcmp(pat + fg->len - 7, "[[:>:]]", 7) == 0) {
+ fg->len -= 14;
+ pat += 7;
+ /* Word boundary is handled separately in util.c */
+ fg->word = true;
+ }
+
+ /*
+ * pat has been adjusted earlier to not include '^', '$' or
+ * the word match character classes at the beginning and ending
+ * of the string respectively.
+ */
+ fg->pattern = grep_malloc(fg->len + 1);
+ memcpy(fg->pattern, pat, fg->len);
+ fg->pattern[fg->len] = '\0';
+
+ /* Look for ways to cheat...er...avoid the full regex engine. */
+ for (i = 0; i < fg->len; i++) {
+ /* Can still cheat? */
+ if (fg->pattern[i] == '.') {
+ hasDot = i;
+ if (i < fg->len / 2) {
+ if (firstHalfDot < 0)
+ /* Closest dot to the beginning */
+ firstHalfDot = i;
+ } else {
+ /* Closest dot to the end of the pattern. */
+ lastHalfDot = i;
+ if (firstLastHalfDot < 0)
+ firstLastHalfDot = i;
+ }
+ } else {
+ /* Free memory and let others know this is empty. */
+ free(fg->pattern);
+ fg->pattern = NULL;
+ return (-1);
+ }
+ }
+
+ /*
+ * Determine if a reverse search would be faster based on the placement
+ * of the dots.
+ */
+ if ((!(lflag || cflag)) && ((!(fg->bol || fg->eol)) &&
+ ((lastHalfDot) && ((firstHalfDot < 0) ||
+ ((fg->len - (lastHalfDot + 1)) < (size_t)firstHalfDot)))) &&
+ !oflag && !color) {
+ fg->reversed = true;
+ hasDot = fg->len - (firstHalfDot < 0 ?
+ firstLastHalfDot : firstHalfDot) - 1;
+ grep_revstr(fg->pattern, fg->len);
+ }
+
+ /*
+ * Normal Quick Search would require a shift based on the position the
+ * next character after the comparison is within the pattern. With
+ * wildcards, the position of the last dot effects the maximum shift
+ * distance.
+ * The closer to the end the wild card is the slower the search. A
+ * reverse version of this algorithm would be useful for wildcards near
+ * the end of the string.
+ *
+ * Examples:
+ * Pattern Max shift
+ * ------- ---------
+ * this 5
+ * .his 4
+ * t.is 3
+ * th.s 2
+ * thi. 1
+ */
+
+ /* Adjust the shift based on location of the last dot ('.'). */
+ shiftPatternLen = fg->len - hasDot;
+
+ /* Preprocess pattern. */
+ for (i = 0; i <= (signed)UCHAR_MAX; i++)
+ fg->qsBc[i] = shiftPatternLen;
+ for (i = hasDot + 1; i < fg->len; i++) {
+ fg->qsBc[fg->pattern[i]] = fg->len - i;
+ }
+
+ /*
+ * Put pattern back to normal after pre-processing to allow for easy
+ * comparisons later.
+ */
+ if (fg->reversed)
+ grep_revstr(fg->pattern, fg->len);
+
+ return (0);
+}
+
+int
+grep_search(fastgrep_t *fg, const unsigned char *data, size_t len, regmatch_t *pmatch)
+{
+ unsigned int j;
+ int ret = REG_NOMATCH;
+
+ if (pmatch->rm_so == (ssize_t)len)
+ return (ret);
+
+ if (fg->bol && pmatch->rm_so != 0) {
+ pmatch->rm_so = len;
+ pmatch->rm_eo = len;
+ return (ret);
+ }
+
+ /* No point in going farther if we do not have enough data. */
+ if (len < fg->len)
+ return (ret);
+
+ /* Only try once at the beginning or ending of the line. */
+ if (fg->bol || fg->eol) {
+ /* Simple text comparison. */
+ /* Verify data is >= pattern length before searching on it. */
+ if (len >= fg->len) {
+ /* Determine where in data to start search at. */
+ j = fg->eol ? len - fg->len : 0;
+ if (!((fg->bol && fg->eol) && (len != fg->len)))
+ if (grep_cmp(fg->pattern, data + j,
+ fg->len) == -1) {
+ pmatch->rm_so = j;
+ pmatch->rm_eo = j + fg->len;
+ ret = 0;
+ }
+ }
+ } else if (fg->reversed) {
+ /* Quick Search algorithm. */
+ j = len;
+ do {
+ if (grep_cmp(fg->pattern, data + j - fg->len,
+ fg->len) == -1) {
+ pmatch->rm_so = j - fg->len;
+ pmatch->rm_eo = j;
+ ret = 0;
+ break;
+ }
+ /* Shift if within bounds, otherwise, we are done. */
+ if (j == fg->len)
+ break;
+ j -= fg->qsBc[data[j - fg->len - 1]];
+ } while (j >= fg->len);
+ } else {
+ /* Quick Search algorithm. */
+ j = pmatch->rm_so;
+ do {
+ if (grep_cmp(fg->pattern, data + j, fg->len) == -1) {
+ pmatch->rm_so = j;
+ pmatch->rm_eo = j + fg->len;
+ ret = 0;
+ break;
+ }
+
+ /* Shift if within bounds, otherwise, we are done. */
+ if (j + fg->len == len)
+ break;
+ else
+ j += fg->qsBc[data[j + fg->len]];
+ } while (j <= (len - fg->len));
+ }
+
+ return (ret);
+}
+
+/*
+ * Returns: i >= 0 on failure (position that it failed)
+ * -1 on success
+ */
+static inline int
+grep_cmp(const unsigned char *pat, const unsigned char *data, size_t len)
+{
+ size_t size;
+ wchar_t *wdata, *wpat;
+ unsigned int i;
+
+ if (iflag) {
+ if ((size = mbstowcs(NULL, (const char *)data, 0)) ==
+ ((size_t) - 1))
+ return (-1);
+
+ wdata = grep_malloc(size * sizeof(wint_t));
+
+ if (mbstowcs(wdata, (const char *)data, size) ==
+ ((size_t) - 1))
+ return (-1);
+
+ if ((size = mbstowcs(NULL, (const char *)pat, 0)) ==
+ ((size_t) - 1))
+ return (-1);
+
+ wpat = grep_malloc(size * sizeof(wint_t));
+
+ if (mbstowcs(wpat, (const char *)pat, size) == ((size_t) - 1))
+ return (-1);
+ for (i = 0; i < len; i++) {
+ if ((towlower(wpat[i]) == towlower(wdata[i])) ||
+ ((grepbehave != GREP_FIXED) && wpat[i] == L'.'))
+ continue;
+ free(wpat);
+ free(wdata);
+ return (i);
+ }
+ } else {
+ for (i = 0; i < len; i++) {
+ if ((pat[i] == data[i]) || ((grepbehave != GREP_FIXED) &&
+ pat[i] == '.'))
+ continue;
+ return (i);
+ }
+ }
+ return (-1);
+}
+
+static inline void
+grep_revstr(unsigned char *str, int len)
+{
+ int i;
+ char c;
+
+ for (i = 0; i < len / 2; i++) {
+ c = str[i];
+ str[i] = str[len - i - 1];
+ str[len - i - 1] = c;
+ }
+}
diff --git a/toolbox/grep/file.c b/toolbox/grep/file.c
new file mode 100644
index 0000000..86b7658
--- /dev/null
+++ b/toolbox/grep/file.c
@@ -0,0 +1,269 @@
+/* $NetBSD: file.c,v 1.7 2011/04/18 22:46:48 joerg Exp $ */
+/* $FreeBSD: head/usr.bin/grep/file.c 211496 2010-08-19 09:28:59Z des $ */
+/* $OpenBSD: file.c,v 1.11 2010/07/02 20:48:48 nicm Exp $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2010 Gabor Kovesdan <gabor@FreeBSD.org>
+ * Copyright (C) 2010 Dimitry Andric <dimitry@andric.com>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: file.c,v 1.7 2011/04/18 22:46:48 joerg Exp $");
+
+#include <sys/param.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+
+#ifndef ANDROID
+#include <bzlib.h>
+#endif
+#include <err.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+#ifndef ANDROID
+#include <zlib.h>
+#endif
+
+#include "grep.h"
+
+#define MAXBUFSIZ (32 * 1024)
+#define LNBUFBUMP 80
+
+#ifndef ANDROID
+static gzFile gzbufdesc;
+static BZFILE* bzbufdesc;
+#endif
+
+static unsigned char buffer[MAXBUFSIZ];
+static unsigned char *bufpos;
+static size_t bufrem;
+
+static unsigned char *lnbuf;
+static size_t lnbuflen;
+
+static inline int
+grep_refill(struct file *f)
+{
+ ssize_t nr;
+ int bzerr;
+
+ bufpos = buffer;
+ bufrem = 0;
+
+#ifndef ANDROID
+ if (filebehave == FILE_GZIP)
+ nr = gzread(gzbufdesc, buffer, MAXBUFSIZ);
+ else if (filebehave == FILE_BZIP && bzbufdesc != NULL) {
+ nr = BZ2_bzRead(&bzerr, bzbufdesc, buffer, MAXBUFSIZ);
+ switch (bzerr) {
+ case BZ_OK:
+ case BZ_STREAM_END:
+ /* No problem, nr will be okay */
+ break;
+ case BZ_DATA_ERROR_MAGIC:
+ /*
+ * As opposed to gzread(), which simply returns the
+ * plain file data, if it is not in the correct
+ * compressed format, BZ2_bzRead() instead aborts.
+ *
+ * So, just restart at the beginning of the file again,
+ * and use plain reads from now on.
+ */
+ BZ2_bzReadClose(&bzerr, bzbufdesc);
+ bzbufdesc = NULL;
+ if (lseek(f->fd, 0, SEEK_SET) == -1)
+ return (-1);
+ nr = read(f->fd, buffer, MAXBUFSIZ);
+ break;
+ default:
+ /* Make sure we exit with an error */
+ nr = -1;
+ }
+ } else
+#endif
+ nr = read(f->fd, buffer, MAXBUFSIZ);
+
+ if (nr < 0)
+ return (-1);
+
+ bufrem = nr;
+ return (0);
+}
+
+static inline int
+grep_lnbufgrow(size_t newlen)
+{
+
+ if (lnbuflen < newlen) {
+ lnbuf = grep_realloc(lnbuf, newlen);
+ lnbuflen = newlen;
+ }
+
+ return (0);
+}
+
+char *
+grep_fgetln(struct file *f, size_t *lenp)
+{
+ unsigned char *p;
+ char *ret;
+ size_t len;
+ size_t off;
+ ptrdiff_t diff;
+
+ /* Fill the buffer, if necessary */
+ if (bufrem == 0 && grep_refill(f) != 0)
+ goto error;
+
+ if (bufrem == 0) {
+ /* Return zero length to indicate EOF */
+ *lenp = 0;
+ return ((char *)bufpos);
+ }
+
+ /* Look for a newline in the remaining part of the buffer */
+ if ((p = memchr(bufpos, line_sep, bufrem)) != NULL) {
+ ++p; /* advance over newline */
+ ret = (char *)bufpos;
+ len = p - bufpos;
+ bufrem -= len;
+ bufpos = p;
+ *lenp = len;
+ return (ret);
+ }
+
+ /* We have to copy the current buffered data to the line buffer */
+ for (len = bufrem, off = 0; ; len += bufrem) {
+ /* Make sure there is room for more data */
+ if (grep_lnbufgrow(len + LNBUFBUMP))
+ goto error;
+ memcpy(lnbuf + off, bufpos, len - off);
+ off = len;
+ if (grep_refill(f) != 0)
+ goto error;
+ if (bufrem == 0)
+ /* EOF: return partial line */
+ break;
+ if ((p = memchr(bufpos, line_sep, bufrem)) == NULL)
+ continue;
+ /* got it: finish up the line (like code above) */
+ ++p;
+ diff = p - bufpos;
+ len += diff;
+ if (grep_lnbufgrow(len))
+ goto error;
+ memcpy(lnbuf + off, bufpos, diff);
+ bufrem -= diff;
+ bufpos = p;
+ break;
+ }
+ *lenp = len;
+ return ((char *)lnbuf);
+
+error:
+ *lenp = 0;
+ return (NULL);
+}
+
+static inline struct file *
+grep_file_init(struct file *f)
+{
+
+#ifndef ANDROID
+ if (filebehave == FILE_GZIP &&
+ (gzbufdesc = gzdopen(f->fd, "r")) == NULL)
+ goto error;
+
+ if (filebehave == FILE_BZIP &&
+ (bzbufdesc = BZ2_bzdopen(f->fd, "r")) == NULL)
+ goto error;
+#endif
+
+ /* Fill read buffer, also catches errors early */
+ if (grep_refill(f) != 0)
+ goto error;
+
+ /* Check for binary stuff, if necessary */
+ if (!nulldataflag && binbehave != BINFILE_TEXT &&
+ memchr(bufpos, '\0', bufrem) != NULL)
+ f->binary = true;
+
+ return (f);
+error:
+ close(f->fd);
+ free(f);
+ return (NULL);
+}
+
+/*
+ * Opens a file for processing.
+ */
+struct file *
+grep_open(const char *path)
+{
+ struct file *f;
+
+ f = grep_malloc(sizeof *f);
+ memset(f, 0, sizeof *f);
+ if (path == NULL) {
+ /* Processing stdin implies --line-buffered. */
+ lbflag = true;
+ f->fd = STDIN_FILENO;
+ } else if ((f->fd = open(path, O_RDONLY)) == -1) {
+ free(f);
+ return (NULL);
+ }
+
+ return (grep_file_init(f));
+}
+
+/*
+ * Closes a file.
+ */
+void
+grep_close(struct file *f)
+{
+
+ close(f->fd);
+
+ /* Reset read buffer and line buffer */
+ bufpos = buffer;
+ bufrem = 0;
+
+ free(lnbuf);
+ lnbuf = NULL;
+ lnbuflen = 0;
+}
diff --git a/toolbox/grep/grep.c b/toolbox/grep/grep.c
new file mode 100644
index 0000000..b5bb2ef
--- /dev/null
+++ b/toolbox/grep/grep.c
@@ -0,0 +1,710 @@
+/* $NetBSD: grep.c,v 1.11 2012/05/06 22:27:00 joerg Exp $ */
+/* $FreeBSD: head/usr.bin/grep/grep.c 211519 2010-08-19 22:55:17Z delphij $ */
+/* $OpenBSD: grep.c,v 1.42 2010/07/02 22:18:03 tedu Exp $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: grep.c,v 1.11 2012/05/06 22:27:00 joerg Exp $");
+
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <ctype.h>
+#include <err.h>
+#include <errno.h>
+#include <getopt.h>
+#include <limits.h>
+#include <libgen.h>
+#include <locale.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "grep.h"
+
+#ifndef WITHOUT_NLS
+#include <nl_types.h>
+nl_catd catalog;
+#endif
+
+/*
+ * Default messags to use when NLS is disabled or no catalogue
+ * is found.
+ */
+const char *errstr[] = {
+ "",
+/* 1*/ "(standard input)",
+/* 2*/ "cannot read bzip2 compressed file",
+/* 3*/ "unknown %s option",
+/* 4*/ "usage: %s [-abcDEFGHhIiJLlmnOoPqRSsUVvwxZz] [-A num] [-B num] [-C[num]]\n",
+/* 5*/ "\t[-e pattern] [-f file] [--binary-files=value] [--color=when]\n",
+/* 6*/ "\t[--context[=num]] [--directories=action] [--label] [--line-buffered]\n",
+/* 7*/ "\t[pattern] [file ...]\n",
+/* 8*/ "Binary file %s matches\n",
+/* 9*/ "%s (BSD grep) %s\n",
+};
+
+/* Flags passed to regcomp() and regexec() */
+int cflags = 0;
+int eflags = REG_STARTEND;
+
+/* Searching patterns */
+unsigned int patterns, pattern_sz;
+char **pattern;
+regex_t *r_pattern;
+fastgrep_t *fg_pattern;
+
+/* Filename exclusion/inclusion patterns */
+unsigned int fpatterns, fpattern_sz;
+unsigned int dpatterns, dpattern_sz;
+struct epat *dpattern, *fpattern;
+
+/* For regex errors */
+char re_error[RE_ERROR_BUF + 1];
+
+/* Command-line flags */
+unsigned long long Aflag; /* -A x: print x lines trailing each match */
+unsigned long long Bflag; /* -B x: print x lines leading each match */
+bool Hflag; /* -H: always print file name */
+bool Lflag; /* -L: only show names of files with no matches */
+bool bflag; /* -b: show block numbers for each match */
+bool cflag; /* -c: only show a count of matching lines */
+bool hflag; /* -h: don't print filename headers */
+bool iflag; /* -i: ignore case */
+bool lflag; /* -l: only show names of files with matches */
+bool mflag; /* -m x: stop reading the files after x matches */
+unsigned long long mcount; /* count for -m */
+bool nflag; /* -n: show line numbers in front of matching lines */
+bool oflag; /* -o: print only matching part */
+bool qflag; /* -q: quiet mode (don't output anything) */
+bool sflag; /* -s: silent mode (ignore errors) */
+bool vflag; /* -v: only show non-matching lines */
+bool wflag; /* -w: pattern must start and end on word boundaries */
+bool xflag; /* -x: pattern must match entire line */
+bool lbflag; /* --line-buffered */
+bool nullflag; /* --null */
+bool nulldataflag; /* --null-data */
+unsigned char line_sep = '\n'; /* 0 for --null-data */
+char *label; /* --label */
+const char *color; /* --color */
+int grepbehave = GREP_BASIC; /* -EFGP: type of the regex */
+int binbehave = BINFILE_BIN; /* -aIU: handling of binary files */
+int filebehave = FILE_STDIO; /* -JZ: normal, gzip or bzip2 file */
+int devbehave = DEV_READ; /* -D: handling of devices */
+int dirbehave = DIR_READ; /* -dRr: handling of directories */
+int linkbehave = LINK_READ; /* -OpS: handling of symlinks */
+
+bool dexclude, dinclude; /* --exclude-dir and --include-dir */
+bool fexclude, finclude; /* --exclude and --include */
+
+enum {
+ BIN_OPT = CHAR_MAX + 1,
+ COLOR_OPT,
+ DECOMPRESS_OPT,
+ HELP_OPT,
+ MMAP_OPT,
+ LINEBUF_OPT,
+ LABEL_OPT,
+ R_EXCLUDE_OPT,
+ R_INCLUDE_OPT,
+ R_DEXCLUDE_OPT,
+ R_DINCLUDE_OPT
+};
+
+static inline const char *init_color(const char *);
+
+/* Housekeeping */
+int tail; /* lines left to print */
+bool notfound; /* file not found */
+
+extern char *__progname;
+
+/*
+ * Prints usage information and returns 2.
+ */
+__dead static void
+usage(void)
+{
+ fprintf(stderr, getstr(4), __progname);
+ fprintf(stderr, "%s", getstr(5));
+ fprintf(stderr, "%s", getstr(5));
+ fprintf(stderr, "%s", getstr(6));
+ fprintf(stderr, "%s", getstr(7));
+ exit(2);
+}
+
+static const char optstr[] =
+ "0123456789A:B:C:D:EFGHIJLOPSRUVZabcd:e:f:hilm:nopqrsuvwxyz";
+
+struct option long_options[] =
+{
+ {"binary-files", required_argument, NULL, BIN_OPT},
+ {"decompress", no_argument, NULL, DECOMPRESS_OPT},
+ {"help", no_argument, NULL, HELP_OPT},
+ {"mmap", no_argument, NULL, MMAP_OPT},
+ {"line-buffered", no_argument, NULL, LINEBUF_OPT},
+ {"label", required_argument, NULL, LABEL_OPT},
+ {"color", optional_argument, NULL, COLOR_OPT},
+ {"colour", optional_argument, NULL, COLOR_OPT},
+ {"exclude", required_argument, NULL, R_EXCLUDE_OPT},
+ {"include", required_argument, NULL, R_INCLUDE_OPT},
+ {"exclude-dir", required_argument, NULL, R_DEXCLUDE_OPT},
+ {"include-dir", required_argument, NULL, R_DINCLUDE_OPT},
+ {"after-context", required_argument, NULL, 'A'},
+ {"text", no_argument, NULL, 'a'},
+ {"before-context", required_argument, NULL, 'B'},
+ {"byte-offset", no_argument, NULL, 'b'},
+ {"context", optional_argument, NULL, 'C'},
+ {"count", no_argument, NULL, 'c'},
+ {"devices", required_argument, NULL, 'D'},
+ {"directories", required_argument, NULL, 'd'},
+ {"extended-regexp", no_argument, NULL, 'E'},
+ {"regexp", required_argument, NULL, 'e'},
+ {"fixed-strings", no_argument, NULL, 'F'},
+ {"file", required_argument, NULL, 'f'},
+ {"basic-regexp", no_argument, NULL, 'G'},
+ {"no-filename", no_argument, NULL, 'h'},
+ {"with-filename", no_argument, NULL, 'H'},
+ {"ignore-case", no_argument, NULL, 'i'},
+ {"bz2decompress", no_argument, NULL, 'J'},
+ {"files-with-matches", no_argument, NULL, 'l'},
+ {"files-without-match", no_argument, NULL, 'L'},
+ {"max-count", required_argument, NULL, 'm'},
+ {"line-number", no_argument, NULL, 'n'},
+ {"only-matching", no_argument, NULL, 'o'},
+ {"quiet", no_argument, NULL, 'q'},
+ {"silent", no_argument, NULL, 'q'},
+ {"recursive", no_argument, NULL, 'r'},
+ {"no-messages", no_argument, NULL, 's'},
+ {"binary", no_argument, NULL, 'U'},
+ {"unix-byte-offsets", no_argument, NULL, 'u'},
+ {"invert-match", no_argument, NULL, 'v'},
+ {"version", no_argument, NULL, 'V'},
+ {"word-regexp", no_argument, NULL, 'w'},
+ {"line-regexp", no_argument, NULL, 'x'},
+ {"null", no_argument, NULL, 'Z'},
+ {"null-data", no_argument, NULL, 'z'},
+ {NULL, no_argument, NULL, 0}
+};
+
+/*
+ * Adds a searching pattern to the internal array.
+ */
+static void
+add_pattern(char *pat, size_t len)
+{
+
+ /* TODO: Check for empty patterns and shortcut */
+
+ /* Increase size if necessary */
+ if (patterns == pattern_sz) {
+ pattern_sz *= 2;
+ pattern = grep_realloc(pattern, ++pattern_sz *
+ sizeof(*pattern));
+ }
+ if (len > 0 && pat[len - 1] == '\n')
+ --len;
+ /* pat may not be NUL-terminated */
+ pattern[patterns] = grep_malloc(len + 1);
+ memcpy(pattern[patterns], pat, len);
+ pattern[patterns][len] = '\0';
+ ++patterns;
+}
+
+/*
+ * Adds a file include/exclude pattern to the internal array.
+ */
+static void
+add_fpattern(const char *pat, int mode)
+{
+
+ /* Increase size if necessary */
+ if (fpatterns == fpattern_sz) {
+ fpattern_sz *= 2;
+ fpattern = grep_realloc(fpattern, ++fpattern_sz *
+ sizeof(struct epat));
+ }
+ fpattern[fpatterns].pat = grep_strdup(pat);
+ fpattern[fpatterns].mode = mode;
+ ++fpatterns;
+}
+
+/*
+ * Adds a directory include/exclude pattern to the internal array.
+ */
+static void
+add_dpattern(const char *pat, int mode)
+{
+
+ /* Increase size if necessary */
+ if (dpatterns == dpattern_sz) {
+ dpattern_sz *= 2;
+ dpattern = grep_realloc(dpattern, ++dpattern_sz *
+ sizeof(struct epat));
+ }
+ dpattern[dpatterns].pat = grep_strdup(pat);
+ dpattern[dpatterns].mode = mode;
+ ++dpatterns;
+}
+
+/*
+ * Reads searching patterns from a file and adds them with add_pattern().
+ */
+static void
+read_patterns(const char *fn)
+{
+ FILE *f;
+ char *line;
+ size_t len;
+ ssize_t rlen;
+
+ if ((f = fopen(fn, "r")) == NULL)
+ err(2, "%s", fn);
+ line = NULL;
+ len = 0;
+#ifndef ANDROID
+ while ((rlen = getline(&line, &len, f)) != -1)
+ add_pattern(line, *line == '\n' ? 0 : (size_t)rlen);
+#endif
+ free(line);
+ if (ferror(f))
+ err(2, "%s", fn);
+ fclose(f);
+}
+
+static inline const char *
+init_color(const char *d)
+{
+ char *c;
+
+ c = getenv("GREP_COLOR");
+ return (c != NULL ? c : d);
+}
+
+int
+grep_main(int argc, char *argv[])
+{
+ char **aargv, **eargv, *eopts;
+ char *ep;
+ unsigned long long l;
+ unsigned int aargc, eargc, i, j;
+ int c, lastc, needpattern, newarg, prevoptind;
+
+ setlocale(LC_ALL, "");
+
+#ifndef WITHOUT_NLS
+ catalog = catopen("grep", NL_CAT_LOCALE);
+#endif
+
+ /* Check what is the program name of the binary. In this
+ way we can have all the funcionalities in one binary
+ without the need of scripting and using ugly hacks. */
+ switch (__progname[0]) {
+ case 'e':
+ grepbehave = GREP_EXTENDED;
+ break;
+ case 'f':
+ grepbehave = GREP_FIXED;
+ break;
+ case 'g':
+ grepbehave = GREP_BASIC;
+ break;
+ case 'z':
+ filebehave = FILE_GZIP;
+ switch(__progname[1]) {
+ case 'e':
+ grepbehave = GREP_EXTENDED;
+ break;
+ case 'f':
+ grepbehave = GREP_FIXED;
+ break;
+ case 'g':
+ grepbehave = GREP_BASIC;
+ break;
+ }
+ break;
+ }
+
+ lastc = '\0';
+ newarg = 1;
+ prevoptind = 1;
+ needpattern = 1;
+
+ eopts = getenv("GREP_OPTIONS");
+
+ /* support for extra arguments in GREP_OPTIONS */
+ eargc = 0;
+ if (eopts != NULL) {
+ char *str;
+
+ /* make an estimation of how many extra arguments we have */
+ for (j = 0; j < strlen(eopts); j++)
+ if (eopts[j] == ' ')
+ eargc++;
+
+ eargv = (char **)grep_malloc(sizeof(char *) * (eargc + 1));
+
+ eargc = 0;
+ /* parse extra arguments */
+ while ((str = strsep(&eopts, " ")) != NULL)
+ eargv[eargc++] = grep_strdup(str);
+
+ aargv = (char **)grep_calloc(eargc + argc + 1,
+ sizeof(char *));
+
+ aargv[0] = argv[0];
+ for (i = 0; i < eargc; i++)
+ aargv[i + 1] = eargv[i];
+ for (j = 1; j < (unsigned int)argc; j++, i++)
+ aargv[i + 1] = argv[j];
+
+ aargc = eargc + argc;
+ } else {
+ aargv = argv;
+ aargc = argc;
+ }
+
+ while (((c = getopt_long(aargc, aargv, optstr, long_options, NULL)) !=
+ -1)) {
+ switch (c) {
+ case '0': case '1': case '2': case '3': case '4':
+ case '5': case '6': case '7': case '8': case '9':
+ if (newarg || !isdigit(lastc))
+ Aflag = 0;
+ else if (Aflag > LLONG_MAX / 10) {
+ errno = ERANGE;
+ err(2, NULL);
+ }
+ Aflag = Bflag = (Aflag * 10) + (c - '0');
+ break;
+ case 'C':
+ if (optarg == NULL) {
+ Aflag = Bflag = 2;
+ break;
+ }
+ /* FALLTHROUGH */
+ case 'A':
+ /* FALLTHROUGH */
+ case 'B':
+ errno = 0;
+ l = strtoull(optarg, &ep, 10);
+ if (((errno == ERANGE) && (l == ULLONG_MAX)) ||
+ ((errno == EINVAL) && (l == 0)))
+ err(2, NULL);
+ else if (ep[0] != '\0') {
+ errno = EINVAL;
+ err(2, NULL);
+ }
+ if (c == 'A')
+ Aflag = l;
+ else if (c == 'B')
+ Bflag = l;
+ else
+ Aflag = Bflag = l;
+ break;
+ case 'a':
+ binbehave = BINFILE_TEXT;
+ break;
+ case 'b':
+ bflag = true;
+ break;
+ case 'c':
+ cflag = true;
+ break;
+ case 'D':
+ if (strcasecmp(optarg, "skip") == 0)
+ devbehave = DEV_SKIP;
+ else if (strcasecmp(optarg, "read") == 0)
+ devbehave = DEV_READ;
+ else
+ errx(2, getstr(3), "--devices");
+ break;
+ case 'd':
+ if (strcasecmp("recurse", optarg) == 0) {
+ Hflag = true;
+ dirbehave = DIR_RECURSE;
+ } else if (strcasecmp("skip", optarg) == 0)
+ dirbehave = DIR_SKIP;
+ else if (strcasecmp("read", optarg) == 0)
+ dirbehave = DIR_READ;
+ else
+ errx(2, getstr(3), "--directories");
+ break;
+ case 'E':
+ grepbehave = GREP_EXTENDED;
+ break;
+ case 'e':
+ add_pattern(optarg, strlen(optarg));
+ needpattern = 0;
+ break;
+ case 'F':
+ grepbehave = GREP_FIXED;
+ break;
+ case 'f':
+ read_patterns(optarg);
+ needpattern = 0;
+ break;
+ case 'G':
+ grepbehave = GREP_BASIC;
+ break;
+ case 'H':
+ Hflag = true;
+ break;
+ case 'h':
+ Hflag = false;
+ hflag = true;
+ break;
+ case 'I':
+ binbehave = BINFILE_SKIP;
+ break;
+ case 'i':
+ case 'y':
+ iflag = true;
+ cflags |= REG_ICASE;
+ break;
+ case 'J':
+ filebehave = FILE_BZIP;
+ break;
+ case 'L':
+ lflag = false;
+ Lflag = true;
+ break;
+ case 'l':
+ Lflag = false;
+ lflag = true;
+ break;
+ case 'm':
+ mflag = true;
+ errno = 0;
+ mcount = strtoull(optarg, &ep, 10);
+ if (((errno == ERANGE) && (mcount == ULLONG_MAX)) ||
+ ((errno == EINVAL) && (mcount == 0)))
+ err(2, NULL);
+ else if (ep[0] != '\0') {
+ errno = EINVAL;
+ err(2, NULL);
+ }
+ break;
+ case 'n':
+ nflag = true;
+ break;
+ case 'O':
+ linkbehave = LINK_EXPLICIT;
+ break;
+ case 'o':
+ oflag = true;
+ break;
+ case 'p':
+ linkbehave = LINK_SKIP;
+ break;
+ case 'q':
+ qflag = true;
+ break;
+ case 'S':
+ linkbehave = LINK_READ;
+ break;
+ case 'R':
+ case 'r':
+ dirbehave = DIR_RECURSE;
+ Hflag = true;
+ break;
+ case 's':
+ sflag = true;
+ break;
+ case 'U':
+ binbehave = BINFILE_BIN;
+ break;
+ case 'u':
+ case MMAP_OPT:
+ /* noop, compatibility */
+ break;
+ case 'V':
+ printf(getstr(9), __progname, VERSION);
+ exit(0);
+ case 'v':
+ vflag = true;
+ break;
+ case 'w':
+ wflag = true;
+ break;
+ case 'x':
+ xflag = true;
+ break;
+ case 'Z':
+ nullflag = true;
+ break;
+ case 'z':
+ nulldataflag = true;
+ line_sep = '\0';
+ break;
+ case BIN_OPT:
+ if (strcasecmp("binary", optarg) == 0)
+ binbehave = BINFILE_BIN;
+ else if (strcasecmp("without-match", optarg) == 0)
+ binbehave = BINFILE_SKIP;
+ else if (strcasecmp("text", optarg) == 0)
+ binbehave = BINFILE_TEXT;
+ else
+ errx(2, getstr(3), "--binary-files");
+ break;
+ case COLOR_OPT:
+ color = NULL;
+ if (optarg == NULL || strcasecmp("auto", optarg) == 0 ||
+ strcasecmp("tty", optarg) == 0 ||
+ strcasecmp("if-tty", optarg) == 0) {
+ char *term;
+
+ term = getenv("TERM");
+ if (isatty(STDOUT_FILENO) && term != NULL &&
+ strcasecmp(term, "dumb") != 0)
+ color = init_color("01;31");
+ } else if (strcasecmp("always", optarg) == 0 ||
+ strcasecmp("yes", optarg) == 0 ||
+ strcasecmp("force", optarg) == 0) {
+ color = init_color("01;31");
+ } else if (strcasecmp("never", optarg) != 0 &&
+ strcasecmp("none", optarg) != 0 &&
+ strcasecmp("no", optarg) != 0)
+ errx(2, getstr(3), "--color");
+ break;
+ case DECOMPRESS_OPT:
+ filebehave = FILE_GZIP;
+ break;
+ case LABEL_OPT:
+ label = optarg;
+ break;
+ case LINEBUF_OPT:
+ lbflag = true;
+ break;
+ case R_INCLUDE_OPT:
+ finclude = true;
+ add_fpattern(optarg, INCL_PAT);
+ break;
+ case R_EXCLUDE_OPT:
+ fexclude = true;
+ add_fpattern(optarg, EXCL_PAT);
+ break;
+ case R_DINCLUDE_OPT:
+ dinclude = true;
+ add_dpattern(optarg, INCL_PAT);
+ break;
+ case R_DEXCLUDE_OPT:
+ dexclude = true;
+ add_dpattern(optarg, EXCL_PAT);
+ break;
+ case HELP_OPT:
+ default:
+ usage();
+ }
+ lastc = c;
+ newarg = optind != prevoptind;
+ prevoptind = optind;
+ }
+ aargc -= optind;
+ aargv += optind;
+
+ /* Fail if we don't have any pattern */
+ if (aargc == 0 && needpattern)
+ usage();
+
+ /* Process patterns from command line */
+ if (aargc != 0 && needpattern) {
+ add_pattern(*aargv, strlen(*aargv));
+ --aargc;
+ ++aargv;
+ }
+
+ switch (grepbehave) {
+ case GREP_FIXED:
+ case GREP_BASIC:
+ break;
+ case GREP_EXTENDED:
+ cflags |= REG_EXTENDED;
+ break;
+ default:
+ /* NOTREACHED */
+ usage();
+ }
+
+ fg_pattern = grep_calloc(patterns, sizeof(*fg_pattern));
+ r_pattern = grep_calloc(patterns, sizeof(*r_pattern));
+/*
+ * XXX: fgrepcomp() and fastcomp() are workarounds for regexec() performance.
+ * Optimizations should be done there.
+ */
+ /* Check if cheating is allowed (always is for fgrep). */
+ if (grepbehave == GREP_FIXED) {
+ for (i = 0; i < patterns; ++i)
+ fgrepcomp(&fg_pattern[i], pattern[i]);
+ } else {
+ for (i = 0; i < patterns; ++i) {
+ if (fastcomp(&fg_pattern[i], pattern[i])) {
+ /* Fall back to full regex library */
+ c = regcomp(&r_pattern[i], pattern[i], cflags);
+ if (c != 0) {
+ regerror(c, &r_pattern[i], re_error,
+ RE_ERROR_BUF);
+ errx(2, "%s", re_error);
+ }
+ }
+ }
+ }
+
+ if (lbflag)
+ setlinebuf(stdout);
+
+ if ((aargc == 0 || aargc == 1) && !Hflag)
+ hflag = true;
+
+ if (aargc == 0)
+ exit(!procfile("-"));
+
+ if (dirbehave == DIR_RECURSE)
+ c = grep_tree(aargv);
+ else
+ for (c = 0; aargc--; ++aargv) {
+ if ((finclude || fexclude) && !file_matching(*aargv))
+ continue;
+ c+= procfile(*aargv);
+ }
+
+#ifndef WITHOUT_NLS
+ catclose(catalog);
+#endif
+
+ /* Find out the correct return value according to the
+ results and the command line option. */
+ exit(c ? (notfound ? (qflag ? 0 : 2) : 0) : (notfound ? 2 : 1));
+}
diff --git a/toolbox/grep/grep.h b/toolbox/grep/grep.h
new file mode 100644
index 0000000..6454f93
--- /dev/null
+++ b/toolbox/grep/grep.h
@@ -0,0 +1,166 @@
+/* $NetBSD: grep.h,v 1.8 2012/05/06 22:27:00 joerg Exp $ */
+/* $OpenBSD: grep.h,v 1.15 2010/04/05 03:03:55 tedu Exp $ */
+/* $FreeBSD: head/usr.bin/grep/grep.h 211496 2010-08-19 09:28:59Z des $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (c) 2008-2009 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#ifdef ANDROID
+#define WITHOUT_NLS
+#endif
+
+#ifndef ANDROID
+#include <bzlib.h>
+#endif
+#include <limits.h>
+#include <regex.h>
+#include <stdbool.h>
+#include <stdio.h>
+#ifndef ANDROID
+#include <zlib.h>
+#endif
+
+#ifdef WITHOUT_NLS
+#define getstr(n) errstr[n]
+#else
+#include <nl_types.h>
+
+extern nl_catd catalog;
+#define getstr(n) catgets(catalog, 1, n, errstr[n])
+#endif
+
+extern const char *errstr[];
+
+#define VERSION "2.5.1-FreeBSD"
+
+#define GREP_FIXED 0
+#define GREP_BASIC 1
+#define GREP_EXTENDED 2
+
+#define BINFILE_BIN 0
+#define BINFILE_SKIP 1
+#define BINFILE_TEXT 2
+
+#define FILE_STDIO 0
+#define FILE_GZIP 1
+#define FILE_BZIP 2
+
+#define DIR_READ 0
+#define DIR_SKIP 1
+#define DIR_RECURSE 2
+
+#define DEV_READ 0
+#define DEV_SKIP 1
+
+#define LINK_READ 0
+#define LINK_EXPLICIT 1
+#define LINK_SKIP 2
+
+#define EXCL_PAT 0
+#define INCL_PAT 1
+
+#define MAX_LINE_MATCHES 32
+
+struct file {
+ int fd;
+ bool binary;
+};
+
+struct str {
+ off_t off;
+ size_t len;
+ char *dat;
+ char *file;
+ int line_no;
+};
+
+struct epat {
+ char *pat;
+ int mode;
+};
+
+typedef struct {
+ size_t len;
+ unsigned char *pattern;
+ int qsBc[UCHAR_MAX + 1];
+ /* flags */
+ bool bol;
+ bool eol;
+ bool reversed;
+ bool word;
+} fastgrep_t;
+
+/* Flags passed to regcomp() and regexec() */
+extern int cflags, eflags;
+
+/* Command line flags */
+extern bool Eflag, Fflag, Gflag, Hflag, Lflag,
+ bflag, cflag, hflag, iflag, lflag, mflag, nflag, oflag,
+ qflag, sflag, vflag, wflag, xflag;
+extern bool dexclude, dinclude, fexclude, finclude, lbflag, nullflag, nulldataflag;
+extern unsigned char line_sep;
+extern unsigned long long Aflag, Bflag, mcount;
+extern char *label;
+extern const char *color;
+extern int binbehave, devbehave, dirbehave, filebehave, grepbehave, linkbehave;
+
+extern bool notfound;
+extern int tail;
+extern unsigned int dpatterns, fpatterns, patterns;
+extern char **pattern;
+extern struct epat *dpattern, *fpattern;
+extern regex_t *er_pattern, *r_pattern;
+extern fastgrep_t *fg_pattern;
+
+/* For regex errors */
+#define RE_ERROR_BUF 512
+extern char re_error[RE_ERROR_BUF + 1]; /* Seems big enough */
+
+/* util.c */
+bool file_matching(const char *fname);
+int procfile(const char *fn);
+int grep_tree(char **argv);
+void *grep_malloc(size_t size);
+void *grep_calloc(size_t nmemb, size_t size);
+void *grep_realloc(void *ptr, size_t size);
+char *grep_strdup(const char *str);
+void printline(struct str *line, int sep, regmatch_t *matches, int m);
+
+/* queue.c */
+void enqueue(struct str *x);
+void printqueue(void);
+void clearqueue(void);
+
+/* file.c */
+void grep_close(struct file *f);
+struct file *grep_open(const char *path);
+char *grep_fgetln(struct file *f, size_t *len);
+
+/* fastgrep.c */
+int fastcomp(fastgrep_t *, const char *);
+void fgrepcomp(fastgrep_t *, const char *);
+int grep_search(fastgrep_t *, const unsigned char *, size_t, regmatch_t *);
diff --git a/toolbox/grep/queue.c b/toolbox/grep/queue.c
new file mode 100644
index 0000000..e3c6be1
--- /dev/null
+++ b/toolbox/grep/queue.c
@@ -0,0 +1,116 @@
+/* $NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $ */
+/* $FreeBSD: head/usr.bin/grep/queue.c 211496 2010-08-19 09:28:59Z des $ */
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * A really poor man's queue. It does only what it has to and gets out of
+ * Dodge. It is used in place of <sys/queue.h> to get a better performance.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: queue.c,v 1.5 2011/08/31 16:24:57 plunky Exp $");
+
+#include <sys/param.h>
+#include <sys/queue.h>
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "grep.h"
+
+struct qentry {
+ STAILQ_ENTRY(qentry) list;
+ struct str data;
+};
+
+static STAILQ_HEAD(, qentry) queue = STAILQ_HEAD_INITIALIZER(queue);
+static unsigned long long count;
+
+static struct qentry *dequeue(void);
+
+void
+enqueue(struct str *x)
+{
+ struct qentry *item;
+
+ item = grep_malloc(sizeof(struct qentry));
+ item->data.dat = grep_malloc(sizeof(char) * x->len);
+ item->data.len = x->len;
+ item->data.line_no = x->line_no;
+ item->data.off = x->off;
+ memcpy(item->data.dat, x->dat, x->len);
+ item->data.file = x->file;
+
+ STAILQ_INSERT_TAIL(&queue, item, list);
+
+ if (++count > Bflag) {
+ item = dequeue();
+ free(item->data.dat);
+ free(item);
+ }
+}
+
+static struct qentry *
+dequeue(void)
+{
+ struct qentry *item;
+
+ item = STAILQ_FIRST(&queue);
+ if (item == NULL)
+ return (NULL);
+
+ STAILQ_REMOVE_HEAD(&queue, list);
+ --count;
+ return (item);
+}
+
+void
+printqueue(void)
+{
+ struct qentry *item;
+
+ while ((item = dequeue()) != NULL) {
+ printline(&item->data, '-', NULL, 0);
+ free(item->data.dat);
+ free(item);
+ }
+}
+
+void
+clearqueue(void)
+{
+ struct qentry *item;
+
+ while ((item = dequeue()) != NULL) {
+ free(item->data.dat);
+ free(item);
+ }
+}
diff --git a/toolbox/grep/util.c b/toolbox/grep/util.c
new file mode 100644
index 0000000..497db06
--- /dev/null
+++ b/toolbox/grep/util.c
@@ -0,0 +1,498 @@
+/* $NetBSD: util.c,v 1.16 2012/05/06 22:32:05 joerg Exp $ */
+/* $FreeBSD: head/usr.bin/grep/util.c 211496 2010-08-19 09:28:59Z des $ */
+/* $OpenBSD: util.c,v 1.39 2010/07/02 22:18:03 tedu Exp $ */
+
+/*-
+ * Copyright (c) 1999 James Howard and Dag-Erling Coïdan Smørgrav
+ * Copyright (C) 2008-2010 Gabor Kovesdan <gabor@FreeBSD.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+#if HAVE_NBTOOL_CONFIG_H
+#include "nbtool_config.h"
+#endif
+
+#include <sys/cdefs.h>
+__RCSID("$NetBSD: util.c,v 1.16 2012/05/06 22:32:05 joerg Exp $");
+
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <ctype.h>
+#include <err.h>
+#include <errno.h>
+#include <fnmatch.h>
+#include <fts.h>
+#include <libgen.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <wchar.h>
+#include <wctype.h>
+
+#include "grep.h"
+
+static bool first, first_global = true;
+static unsigned long long since_printed;
+
+static int procline(struct str *l, int);
+
+bool
+file_matching(const char *fname)
+{
+ char *fname_base, *fname_copy;
+ unsigned int i;
+ bool ret;
+
+ ret = finclude ? false : true;
+ fname_copy = grep_strdup(fname);
+ fname_base = basename(fname_copy);
+
+ for (i = 0; i < fpatterns; ++i) {
+ if (fnmatch(fpattern[i].pat, fname, 0) == 0 ||
+ fnmatch(fpattern[i].pat, fname_base, 0) == 0) {
+ if (fpattern[i].mode == EXCL_PAT)
+ return (false);
+ else
+ ret = true;
+ }
+ }
+ free(fname_copy);
+ return (ret);
+}
+
+static inline bool
+dir_matching(const char *dname)
+{
+ unsigned int i;
+ bool ret;
+
+ ret = dinclude ? false : true;
+
+ for (i = 0; i < dpatterns; ++i) {
+ if (dname != NULL &&
+ fnmatch(dname, dpattern[i].pat, 0) == 0) {
+ if (dpattern[i].mode == EXCL_PAT)
+ return (false);
+ else
+ ret = true;
+ }
+ }
+ return (ret);
+}
+
+/*
+ * Processes a directory when a recursive search is performed with
+ * the -R option. Each appropriate file is passed to procfile().
+ */
+int
+grep_tree(char **argv)
+{
+ FTS *fts;
+ FTSENT *p;
+ char *d, *dir = NULL;
+ int c, fts_flags;
+ bool ok;
+
+ c = fts_flags = 0;
+
+ switch(linkbehave) {
+ case LINK_EXPLICIT:
+ fts_flags = FTS_COMFOLLOW;
+ break;
+ case LINK_SKIP:
+ fts_flags = FTS_PHYSICAL;
+ break;
+ default:
+ fts_flags = FTS_LOGICAL;
+
+ }
+
+ fts_flags |= FTS_NOSTAT | FTS_NOCHDIR;
+
+ if (!(fts = fts_open(argv, fts_flags, NULL)))
+ err(2, "fts_open");
+ while ((p = fts_read(fts)) != NULL) {
+ switch (p->fts_info) {
+ case FTS_DNR:
+ /* FALLTHROUGH */
+ case FTS_ERR:
+ errx(2, "%s: %s", p->fts_path, strerror(p->fts_errno));
+ break;
+ case FTS_D:
+ /* FALLTHROUGH */
+ case FTS_DP:
+ break;
+ case FTS_DC:
+ /* Print a warning for recursive directory loop */
+ warnx("warning: %s: recursive directory loop",
+ p->fts_path);
+ break;
+ default:
+ /* Check for file exclusion/inclusion */
+ ok = true;
+ if (dexclude || dinclude) {
+ if ((d = strrchr(p->fts_path, '/')) != NULL) {
+ dir = grep_malloc(sizeof(char) *
+ (d - p->fts_path + 1));
+ memcpy(dir, p->fts_path,
+ d - p->fts_path);
+ dir[d - p->fts_path] = '\0';
+ }
+ ok = dir_matching(dir);
+ free(dir);
+ dir = NULL;
+ }
+ if (fexclude || finclude)
+ ok &= file_matching(p->fts_path);
+
+ if (ok)
+ c += procfile(p->fts_path);
+ break;
+ }
+ }
+
+ fts_close(fts);
+ return (c);
+}
+
+/*
+ * Opens a file and processes it. Each file is processed line-by-line
+ * passing the lines to procline().
+ */
+int
+procfile(const char *fn)
+{
+ struct file *f;
+ struct stat sb;
+ struct str ln;
+ mode_t s;
+ int c, t;
+
+ if (mflag && (mcount <= 0))
+ return (0);
+
+ if (strcmp(fn, "-") == 0) {
+ fn = label != NULL ? label : getstr(1);
+ f = grep_open(NULL);
+ } else {
+ if (!stat(fn, &sb)) {
+ /* Check if we need to process the file */
+ s = sb.st_mode & S_IFMT;
+ if (s == S_IFDIR && dirbehave == DIR_SKIP)
+ return (0);
+ if ((s == S_IFIFO || s == S_IFCHR || s == S_IFBLK
+ || s == S_IFSOCK) && devbehave == DEV_SKIP)
+ return (0);
+ }
+ f = grep_open(fn);
+ }
+ if (f == NULL) {
+ if (!sflag)
+ warn("%s", fn);
+ if (errno == ENOENT)
+ notfound = true;
+ return (0);
+ }
+
+ ln.file = grep_malloc(strlen(fn) + 1);
+ strcpy(ln.file, fn);
+ ln.line_no = 0;
+ ln.len = 0;
+ tail = 0;
+ ln.off = -1;
+
+ for (first = true, c = 0; c == 0 || !(lflag || qflag); ) {
+ ln.off += ln.len + 1;
+ if ((ln.dat = grep_fgetln(f, &ln.len)) == NULL || ln.len == 0)
+ break;
+ if (ln.len > 0 && ln.dat[ln.len - 1] == line_sep)
+ --ln.len;
+ ln.line_no++;
+
+ /* Return if we need to skip a binary file */
+ if (f->binary && binbehave == BINFILE_SKIP) {
+ grep_close(f);
+ free(ln.file);
+ free(f);
+ return (0);
+ }
+ /* Process the file line-by-line */
+ t = procline(&ln, f->binary);
+ c += t;
+
+ /* Count the matches if we have a match limit */
+ if (mflag) {
+ mcount -= t;
+ if (mcount <= 0)
+ break;
+ }
+ }
+ if (Bflag > 0)
+ clearqueue();
+ grep_close(f);
+
+ if (cflag) {
+ if (!hflag)
+ printf("%s:", ln.file);
+ printf("%u%c", c, line_sep);
+ }
+ if (lflag && !qflag && c != 0)
+ printf("%s%c", fn, line_sep);
+ if (Lflag && !qflag && c == 0)
+ printf("%s%c", fn, line_sep);
+ if (c && !cflag && !lflag && !Lflag &&
+ binbehave == BINFILE_BIN && f->binary && !qflag)
+ printf(getstr(8), fn);
+
+ free(ln.file);
+ free(f);
+ return (c);
+}
+
+#define iswword(x) (iswalnum((x)) || (x) == L'_')
+
+/*
+ * Processes a line comparing it with the specified patterns. Each pattern
+ * is looped to be compared along with the full string, saving each and every
+ * match, which is necessary to colorize the output and to count the
+ * matches. The matching lines are passed to printline() to display the
+ * appropriate output.
+ */
+static int
+procline(struct str *l, int nottext)
+{
+ regmatch_t matches[MAX_LINE_MATCHES];
+ regmatch_t pmatch;
+ size_t st = 0;
+ unsigned int i;
+ int c = 0, m = 0, r = 0;
+
+ /* Loop to process the whole line */
+ while (st <= l->len) {
+ pmatch.rm_so = st;
+ pmatch.rm_eo = l->len;
+
+ /* Loop to compare with all the patterns */
+ for (i = 0; i < patterns; i++) {
+/*
+ * XXX: grep_search() is a workaround for speed up and should be
+ * removed in the future. See fastgrep.c.
+ */
+ if (fg_pattern[i].pattern) {
+ r = grep_search(&fg_pattern[i],
+ (unsigned char *)l->dat,
+ l->len, &pmatch);
+ r = (r == 0) ? 0 : REG_NOMATCH;
+ st = pmatch.rm_eo;
+ } else {
+ r = regexec(&r_pattern[i], l->dat, 1,
+ &pmatch, eflags);
+ r = (r == 0) ? 0 : REG_NOMATCH;
+ st = pmatch.rm_eo;
+ }
+ if (r == REG_NOMATCH)
+ continue;
+ /* Check for full match */
+ if (xflag &&
+ (pmatch.rm_so != 0 ||
+ (size_t)pmatch.rm_eo != l->len))
+ continue;
+ /* Check for whole word match */
+ if (fg_pattern[i].word && pmatch.rm_so != 0) {
+ wint_t wbegin, wend;
+
+ wbegin = wend = L' ';
+ if (pmatch.rm_so != 0 &&
+ sscanf(&l->dat[pmatch.rm_so - 1],
+ "%lc", &wbegin) != 1)
+ continue;
+ if ((size_t)pmatch.rm_eo != l->len &&
+ sscanf(&l->dat[pmatch.rm_eo],
+ "%lc", &wend) != 1)
+ continue;
+ if (iswword(wbegin) || iswword(wend))
+ continue;
+ }
+ c = 1;
+ if (m < MAX_LINE_MATCHES)
+ matches[m++] = pmatch;
+ /* matches - skip further patterns */
+ if ((color != NULL && !oflag) || qflag || lflag)
+ break;
+ }
+
+ if (vflag) {
+ c = !c;
+ break;
+ }
+ /* One pass if we are not recording matches */
+ if ((color != NULL && !oflag) || qflag || lflag)
+ break;
+
+ if (st == (size_t)pmatch.rm_so)
+ break; /* No matches */
+ }
+
+ if (c && binbehave == BINFILE_BIN && nottext)
+ return (c); /* Binary file */
+
+ /* Dealing with the context */
+ if ((tail || c) && !cflag && !qflag && !lflag && !Lflag) {
+ if (c) {
+ if ((Aflag || Bflag) && !first_global &&
+ (first || since_printed > Bflag))
+ printf("--\n");
+ tail = Aflag;
+ if (Bflag > 0)
+ printqueue();
+ printline(l, ':', matches, m);
+ } else {
+ printline(l, '-', matches, m);
+ tail--;
+ }
+ first = false;
+ first_global = false;
+ since_printed = 0;
+ } else {
+ if (Bflag)
+ enqueue(l);
+ since_printed++;
+ }
+ return (c);
+}
+
+/*
+ * Safe malloc() for internal use.
+ */
+void *
+grep_malloc(size_t size)
+{
+ void *ptr;
+
+ if ((ptr = malloc(size)) == NULL)
+ err(2, "malloc");
+ return (ptr);
+}
+
+/*
+ * Safe calloc() for internal use.
+ */
+void *
+grep_calloc(size_t nmemb, size_t size)
+{
+ void *ptr;
+
+ if ((ptr = calloc(nmemb, size)) == NULL)
+ err(2, "calloc");
+ return (ptr);
+}
+
+/*
+ * Safe realloc() for internal use.
+ */
+void *
+grep_realloc(void *ptr, size_t size)
+{
+
+ if ((ptr = realloc(ptr, size)) == NULL)
+ err(2, "realloc");
+ return (ptr);
+}
+
+/*
+ * Safe strdup() for internal use.
+ */
+char *
+grep_strdup(const char *str)
+{
+ char *ret;
+
+ if ((ret = strdup(str)) == NULL)
+ err(2, "strdup");
+ return (ret);
+}
+
+/*
+ * Prints a matching line according to the command line options.
+ */
+void
+printline(struct str *line, int sep, regmatch_t *matches, int m)
+{
+ size_t a = 0;
+ int i, n = 0;
+
+ if (!hflag) {
+ if (nullflag == 0)
+ fputs(line->file, stdout);
+ else {
+ printf("%s", line->file);
+ putchar(0);
+ }
+ ++n;
+ }
+ if (nflag) {
+ if (n > 0)
+ putchar(sep);
+ printf("%d", line->line_no);
+ ++n;
+ }
+ if (bflag) {
+ if (n > 0)
+ putchar(sep);
+ printf("%lld", (long long)line->off);
+ ++n;
+ }
+ if (n)
+ putchar(sep);
+ /* --color and -o */
+ if ((oflag || color) && m > 0) {
+ for (i = 0; i < m; i++) {
+ if (!oflag)
+ fwrite(line->dat + a, matches[i].rm_so - a, 1,
+ stdout);
+ if (color)
+ fprintf(stdout, "\33[%sm\33[K", color);
+
+ fwrite(line->dat + matches[i].rm_so,
+ matches[i].rm_eo - matches[i].rm_so, 1,
+ stdout);
+ if (color)
+ fprintf(stdout, "\33[m\33[K");
+ a = matches[i].rm_eo;
+ if (oflag)
+ putchar('\n');
+ }
+ if (!oflag) {
+ if (line->len - a > 0)
+ fwrite(line->dat + a, line->len - a, 1, stdout);
+ putchar(line_sep);
+ }
+ } else {
+ fwrite(line->dat, line->len, 1, stdout);
+ putchar(line_sep);
+ }
+}