optimize.R

B <- 36	# size of filename alphabet

# Closed-form formula for sum(nchar(filename_for_index(0..(n-1)))), the sum of
# the first n filenames generated by filename_for_index.
#
# First, pretend like filename_for_index generates a zero-length
# filename at index 0, and shift the other indices by 1. This doesn't
# affect the sum of lengths, and makes the formula more regular. Now, of
# the first n filenames, all but 1 are at least 1 byte long, all but
# 36+1 are at least 2 bytes long, all but 36²+36+1 are at least 3 bytes
# long, and so on. In general, for a length i, all but 36^(i-1)+...+1 =
# (36^i-1)/35 (a base-36 repunit) filenames are at least i bytes long.
# The greatest value of i that does not exceed the length of the nth
# filename is
#   d = floor(log_36(n/(36/35))) + 1
# For each value of i, we add 1 byte for each filename that is at least
# i bytes long.
#   Σ_i=1…d n - (36^i-1)/35
#   = dn - Σ_i=1…d (36^i-1)/35
#   = dn - ((36^d-1)*36/35² - d/35)
# where the last equality comes from adapting a formula for the sum of
# base-10 repunits: https://oeis.org/A014824.
sum_filename_lengths <- function(n) {
	n <- n + 1 # Shift by 1 index for a fictitious zero-length filename.
	B1 <- B - 1
	# Length of the longest base-B repunit not greater than n
	d <- floor(log(n/(B/B1), B)) + 1
	d*n - ((B^d-1)/B1 * B/B1 - d/B1)
}

# Calculates sum(nchar(filename_for_index(i)) * i) for i in 0..(n-1), but in a
# faster way (O(log n)) than just doing the sum.
triangular_sum_filename_lengths <- Vectorize(function(n) {
	s <- 0
	m <- 1
	r <- -1
	# s is the running sum. m is the current filename length (starts at 1).
	# r keeps track of the starting point for weighting the summation in
	# each iteration; it starts at -1, not 0, because we are weighting the
	# filenames by 0:(n-1), not 1:n.
	while (n > 0) {
		# x is the number of filenames of length m: either B^m, or
		# however many remain.
		x <- min(n, B^m)
		# x * (x+1)/2 is 1 + 2 + ... + x.
		# x * ((x+1)/2 + r) is (r+1) + (r+2) + ... + (r+x).
		s <- s + m * x * ((x + 1) / 2 + r)
		# We've handled all x filenames of length m.
		n <- n - x
		# Next iteration, offset weights by the number of filenames we
		# have just processed.
		r <- r + x
		# Next filename length.
		m <- m + 1
	}
	s
})


argmax_fn <- function(range, f) {
	range[[which.max(f(range))]]
}

# find the smallest value for which f returns true, or else NA
bsearch_fn <- function(low, high, f) {
	low <- floor(low)
	hight <- ceiling(high)
	while (is.na(high) || low < high) {
		if (is.na(high)) {
			mid <- low * 2
		} else {
			mid <- floor((low + high) / 2)
		}
		if (!f(mid)) {
			low <- mid + 1
		} else {
			high <- mid
		}
	}
	ifelse(f(low), low, NA)
}

# elementwise min and max of each element of a vector with a bound.
cmin <- function(v, bound) {
	sapply(v, function(e) min(e, bound))
}
cmax <- function(v, bound) {
	sapply(v, function(e) max(e, bound))
}


lfh <- 30	# size of a local file header
cdh <- 46	# size of a central directory header
eocd <- 22	# size of an end of central directory record
quot_ext <- 4	# size of a an extra field tag/length header (for quoting)
quot_def <- 5	# size of a DEFLATE non-compressed block header (for quoting)

lfh_zip64 <- lfh+20
cdh_zip64 <- cdh+12
eocd_zip64 <- eocd+56+20	# Zip64 end of central directory record and end of central directory locator

# See how many files we can quote using extra fields rather than DEFLATE
# non-compressed blocks.
max_num_quot_ext <- bsearch_fn(1, NA, function(n) {
	n*lfh + (n-1)*quot_ext + sum_filename_lengths(n) > 65535
}) - 1
max_num_quot_ext_zip64 <- bsearch_fn(1, NA, function(n) {
	n*lfh_zip64 + (n-1)*quot_ext + sum_filename_lengths(n) > 65535
}) - 1

DEFLATE_uncompressed_size_given_compressed_size <- function(compressed_size) {
	# This relies on specific knowledge of how bulk_deflate works,
	# specifically that the prefix and suffix are together 16 bytes long
	# and automatically represent 1033 uncompressed bytes by themselves
	# (1+258+258 in the prefix and 258+258 in the suffix).
	1033 + (compressed_size-16) * 1032
}

DEFLATE_compressed_size_given_uncompressed_size <- function(uncompressed_size) {
	# Account for prefix and suffix.
	15 + 1 + ceiling((uncompressed_size-1-1032) / 1032)
}

DEFLATE_uncompressed_size_given_max_uncompressed_size <- function(max_uncompressed_size) {
	# bulk_deflate will get within 258 of max_uncompressed_size (accounting
	# for the 1 literal byte at the beginning).
	max_uncompressed_size - ((max_uncompressed_size-1) %% 258)
}

BZIP2_uncompressed_size_given_compressed_size <- function(compressed_size) {
	(compressed_size-4-10) * 45899235 / 32
}

BZIP2_compressed_size_given_max_compressed_size <- function(max_compressed_size) {
	4 + ((max_compressed_size-4-10) %/% 32) * 32 + 10
}

BZIP2_compressed_size_given_max_uncompressed_size <- function(max_uncompressed_size) {
	4 + (max_uncompressed_size %/% 45899235) * 32 + 10
}


## full overlap construction

FULL_headers_size <- function(num_files) {
	lfh + num_files*cdh + sum_filename_lengths(1) + sum_filename_lengths(num_files) + eocd
}

FULL_zipped_size_given_compressed_size <- function(compressed_size, num_files) {
	compressed_size + FULL_headers_size(num_files)
}

FULL_unzipped_size_given_uncompressed_size <- function(uncompressed_size, num_files) {
	num_files*uncompressed_size
}

FULL_DEFLATE_unzipped_size_given_compressed_size <- function(compressed_size, num_files) {
	uncompressed_size <- DEFLATE_uncompressed_size_given_compressed_size(compressed_size)
	FULL_unzipped_size_given_uncompressed_size(uncompressed_size, num_files)
}

FULL_BZIP2_unzipped_size_given_compressed_size <- function(compressed_size, num_files) {
	uncompressed_size <- BZIP2_uncompressed_size_given_compressed_size(compressed_size)
	FULL_unzipped_size_given_uncompressed_size(uncompressed_size, num_files)
}

FULL_64_headers_size <- function(num_files) {
	lfh_zip64 + num_files*cdh_zip64 + sum_filename_lengths(1) + sum_filename_lengths(num_files) + eocd_zip64
}

FULL_64_zipped_size_given_compressed_size <- function(compressed_size, num_files) {
	compressed_size + FULL_64_headers_size(num_files)
}


## quoted overlap construction

QUOTED_headers_size <- function(num_files, extra_quoting) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	num_files*(lfh+cdh) + num_quot_ext*quot_ext + num_quot_def*quot_def + 2*sum_filename_lengths(num_files) + eocd
}

QUOTED_zipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	compressed_size + QUOTED_headers_size(num_files, extra_quoting)
}

QUOTED_unzipped_size_given_uncompressed_size <- function(uncompressed_size, num_files, extra_quoting) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	num_files*uncompressed_size + num_quot_ext*num_quot_def*lfh + num_quot_def*(num_quot_def+1)/2*lfh + triangular_sum_filename_lengths(num_files) - triangular_sum_filename_lengths(num_quot_ext+1)
}

QUOTED_DEFLATE_unzipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	uncompressed_size <- DEFLATE_uncompressed_size_given_compressed_size(compressed_size)
	QUOTED_unzipped_size_given_uncompressed_size(uncompressed_size, num_files, extra_quoting)
}

QUOTED_DEFLATE_zipped_size_given_max_uncompressed_size <- function(max_uncompressed_size, num_files, extra_quoting=FALSE) {
	uncompressed_size <- DEFLATE_uncompressed_size_given_max_uncompressed_size(max_uncompressed_size)
	compressed_size <- DEFLATE_compressed_size_given_uncompressed_size(uncompressed_size)
	QUOTED_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
}

QUOTED_DEFLATE_unzipped_size_given_max_uncompressed_size <- function(max_uncompressed_size, num_files, extra_quoting=FALSE) {
	uncompressed_size <- DEFLATE_uncompressed_size_given_max_uncompressed_size(max_uncompressed_size)
	QUOTED_unzipped_size_given_uncompressed_size(uncompressed_size, num_files, extra_quoting)
}

QUOTED_BZIP2_unzipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	uncompressed_size <- BZIP2_uncompressed_size_given_compressed_size(compressed_size)
	QUOTED_unzipped_size_given_uncompressed_size(uncompressed_size, num_files, extra_quoting)
}

QUOTED_64_headers_size <- function(num_files, extra_quoting) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext_zip64) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	num_files*(lfh_zip64+cdh_zip64) + num_quot_ext*quot_ext + num_quot_def*quot_def + 2*sum_filename_lengths(num_files) + eocd_zip64
}

QUOTED_64_zipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	compressed_size + QUOTED_64_headers_size(num_files, extra_quoting)
}

QUOTED_64_unzipped_size_given_uncompressed_size <- function(uncompressed_size, num_files, extra_quoting) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext_zip64) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	num_files*uncompressed_size + num_quot_ext*num_quot_def*lfh_zip64 + num_quot_def*(num_quot_def+1)/2*lfh_zip64 + triangular_sum_filename_lengths(num_files) - triangular_sum_filename_lengths(num_quot_ext+1)
}

QUOTED_DEFLATE_64_unzipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	uncompressed_size <- DEFLATE_uncompressed_size_given_compressed_size(compressed_size)
	QUOTED_64_unzipped_size_given_uncompressed_size(uncompressed_size, num_files, extra_quoting)
}

QUOTED_BZIP2_64_unzipped_size_given_compressed_size <- function(compressed_size, num_files, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	uncompressed_size <- BZIP2_uncompressed_size_given_compressed_size(compressed_size)
	QUOTED_64_unzipped_size_given_uncompressed_size(uncompressed_size, num_files, extra_quoting)
}

QUOTED_BZIP2_zipped_size_given_max_uncompressed_size <- function(max_uncompressed_size, num_files, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	compressed_size <- BZIP2_compressed_size_given_max_uncompressed_size(max_uncompressed_size)
	QUOTED_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
}

QUOTED_BZIP2_unzipped_size_given_max_uncompressed_size <- function(max_uncompressed_size, num_files, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	compressed_size <- BZIP2_compressed_size_given_max_uncompressed_size(max_uncompressed_size)
	QUOTED_BZIP2_unzipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
}


## optimization

FULL_DEFLATE_optimize_for_zipped_size <- function(zipped_size) {
	num_files_opt <- argmax_fn(1:(zipped_size/cdh), function(num_files) {
		compressed_size <- zipped_size - FULL_headers_size(num_files)
		FULL_DEFLATE_unzipped_size_given_compressed_size(compressed_size, num_files) / FULL_zipped_size_given_compressed_size(compressed_size, num_files)
	})
	compressed_size_opt <- zipped_size - FULL_headers_size(num_files_opt)
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

FULL_BZIP2_optimize_for_max_zipped_size <- function(max_zipped_size) {
	num_files_opt <- argmax_fn(1:(max_zipped_size/cdh), function(num_files) {
		compressed_size <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - FULL_headers_size(num_files))
		FULL_BZIP2_unzipped_size_given_compressed_size(compressed_size, num_files) / FULL_zipped_size_given_compressed_size(compressed_size, num_files)
	})
	compressed_size_opt <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - FULL_headers_size(num_files_opt))
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

FULL_BZIP2_64_optimize_for_max_zipped_size <- function(max_zipped_size) {
	num_files_opt <- argmax_fn(1:(max_zipped_size/cdh), function(num_files) {
		compressed_size <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - FULL_64_headers_size(num_files))
		FULL_BZIP2_unzipped_size_given_compressed_size(compressed_size, num_files) / FULL_64_zipped_size_given_compressed_size(compressed_size, num_files)
	})
	compressed_size_opt <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - FULL_64_headers_size(num_files_opt))
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

QUOTED_DEFLATE_optimize_for_zipped_size <- function(zipped_size, extra_quoting=FALSE) {
	num_files_opt <- argmax_fn(1:(zipped_size/(lfh+cdh+quot_ext)), function(num_files) {
		compressed_size <- zipped_size - QUOTED_headers_size(num_files, extra_quoting)
		QUOTED_DEFLATE_unzipped_size_given_compressed_size(compressed_size, num_files, extra_quoting) / QUOTED_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
	})
	compressed_size_opt <- zipped_size - QUOTED_headers_size(num_files_opt, extra_quoting)
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

QUOTED_DEFLATE_optimize_for_num_files <- function(num_files, extra_quoting=FALSE) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	# 2^32 - 2 is the maximum representable file size. (Not 2^32 - 1, because Go archive/zip formerly (https://github.com/golang/go/issues/14185) and yauzl 2.10.0 still (https://github.com/thejoshwolfe/yauzl/blob/2.10.0/index.js#L333-L348) takes it to mean Zip64 headers must be present.)
	# lfh*(num_quot_def) is the file size increase from quoting num_quot_def local file headers.
	# sum_filename_lengths(num_files) - sum_filename_lengths(num_files-num_quot_def) is the file size increase from DEFLATE quoting of filenames.
	max_uncompressed_size <- 2^32 - 2 - (lfh*num_quot_def + sum_filename_lengths(num_files) - sum_filename_lengths(num_files-num_quot_def))
	# The compression ratio is not monotonic in max_uncompressed_size. Omitting one
	# pair of 0 bits decreases the zipped size by 258*65535 ≈ 17 MB, but it is
	# worth it if omitting those bits saves one byte in the DEFLATE suffix.
	# So try our absolute maximum limit minus 0, 258, 516, 774.
	max_uncompressed_size_opt <- argmax_fn(seq(max_uncompressed_size, max_uncompressed_size-1032, -258), function(max_uncompressed_size) {
		QUOTED_DEFLATE_unzipped_size_given_max_uncompressed_size(max_uncompressed_size, num_files, extra_quoting) / QUOTED_DEFLATE_zipped_size_given_max_uncompressed_size(max_uncompressed_size, num_files, extra_quoting)
	})
	list(max_uncompressed_size=max_uncompressed_size_opt, num_files=num_files)
}

QUOTED_DEFLATE_64_optimize_for_zipped_size <- function(zipped_size, extra_quoting=FALSE) {
	max_num_files <- (zipped_size-eocd_zip64)/(lfh_zip64+cdh_zip64+quot_ext)
	low <- max(0, floor(max_num_files/2 - max(max_num_files * 0.05, 10)))
	high <- min(max_num_files, floor(max_num_files/2 + max(max_num_files * 0.05, 10)))
	num_files_opt <- argmax_fn(low:high, function(num_files) {
		compressed_size <- zipped_size - QUOTED_64_headers_size(num_files, extra_quoting)
		QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(compressed_size, num_files, extra_quoting) / QUOTED_64_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
	})
	compressed_size_opt <- zipped_size - QUOTED_64_headers_size(num_files_opt, extra_quoting)
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

QUOTED_BZIP2_optimize_for_max_zipped_size <- function(max_zipped_size, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	num_files_opt <- argmax_fn(1:(max_zipped_size/(lfh+cdh+quot_ext)), function(num_files) {
		compressed_size <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - QUOTED_headers_size(num_files, extra_quoting))
		QUOTED_BZIP2_unzipped_size_given_compressed_size(compressed_size, num_files, extra_quoting) / QUOTED_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
	})
	compressed_size_opt <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - QUOTED_headers_size(num_files_opt, extra_quoting))
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

QUOTED_BZIP2_optimize_for_num_files <- function(num_files, extra_quoting=TRUE) {
	if (!extra_quoting)
		stop()
	# bzip2 allows only extra-field quoting, not DEFLATE quoting, so there is no file size expansion.
	list(max_uncompressed_size=2^32 - 2, num_files=num_files)
}

QUOTED_BZIP2_64_optimize_for_max_zipped_size <- function(max_zipped_size, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	num_files_opt <- argmax_fn(1:(max_zipped_size/(lfh_zip64+cdh_zip64+quot_ext)), function(num_files) {
		compressed_size <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - QUOTED_64_headers_size(num_files, extra_quoting))
		QUOTED_BZIP2_64_unzipped_size_given_compressed_size(compressed_size, num_files, extra_quoting) / QUOTED_64_zipped_size_given_compressed_size(compressed_size, num_files, extra_quoting)
	})
	compressed_size_opt <- BZIP2_compressed_size_given_max_compressed_size(max_zipped_size - QUOTED_64_headers_size(num_files_opt, extra_quoting))
	list(compressed_size=compressed_size_opt, num_files=num_files_opt)
}

cat("\n\noptimize overlap.zip\n")
params <- FULL_DEFLATE_optimize_for_zipped_size(42374)
params
print(c("zipped size", FULL_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", FULL_DEFLATE_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

cat("\n\noptimize bzip2 overlap\n")
params <- FULL_BZIP2_optimize_for_max_zipped_size(1024)
params
print(c("zipped size", FULL_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", FULL_BZIP2_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

# bzip2 quoted overlap only works with extra-field quoting.
cat("\n\noptimize bzip2 quoted overlap\n")
params <- QUOTED_BZIP2_optimize_for_max_zipped_size(1024, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_BZIP2_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
BZIP2_uncompressed_size_given_compressed_size(params$compressed_size)

cat("\n\noptimize bzip2 zip64\n")
params <- QUOTED_BZIP2_64_optimize_for_max_zipped_size(42374, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_BZIP2_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))

cat("\n\noptimize bzip2 quoted overlap non-zip64 max\n")
params <- QUOTED_BZIP2_optimize_for_num_files(max_num_quot_ext+1, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_BZIP2_zipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_BZIP2_unzipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files, extra_quoting=TRUE)))

cat("\n\noptimize bzip2 overlap zip64\n")
params <- FULL_BZIP2_64_optimize_for_max_zipped_size(1000000)
params
print(c("zipped size", FULL_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", FULL_BZIP2_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

cat("\n\noptimize zbsm.zip\n")
params <- QUOTED_DEFLATE_optimize_for_zipped_size(42374)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

cat("\n\noptimize zbsm.zip with extra-field quoting\n")
params <- QUOTED_DEFLATE_optimize_for_zipped_size(42374, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))

cat("\n\noptimize zblg.zip\n")
# 65534, not 65535, because yauzl 2.10.0 requires Zip64 format with 65535 files: https://github.com/thejoshwolfe/yauzl/issues/108
params <- QUOTED_DEFLATE_optimize_for_num_files(65534)
params
print(c("zipped size", QUOTED_DEFLATE_zipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files)))

cat("\n\noptimize zblg.zip with extra-field quoting\n")
params <- QUOTED_DEFLATE_optimize_for_num_files(65534, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_DEFLATE_zipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_max_uncompressed_size(params$max_uncompressed_size, params$num_files, extra_quoting=TRUE)))

cat("\n\noptimize zbxl.zip\n")
# Binary search for the smallest zipped_size that gets an unzipped_size greater
# than the full recursive unzipped size of 42.zip.
zipped_size_opt <- bsearch_fn(10*1024*1024, 100*1024*1024, function(zipped_size) {
	params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size)
	unzipped_size <- QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)
	unzipped_size >= 4507981343026016
})
params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size_opt)
params
print(c("zipped size", QUOTED_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

cat("\n\noptimize zbxl.zip with extra-field quoting\n")
# Binary search for the smallest zipped_size that gets an unzipped_size greater
# than the full recursive unzipped size of 42.zip.
zipped_size_opt <- bsearch_fn(10*1024*1024, 100*1024*1024, function(zipped_size) {
	params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size, extra_quoting=TRUE)
	unzipped_size <- QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)
	unzipped_size >= 4507981343026016
})
params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size_opt, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))

cat("\n\noptimize zbxxl.zip\n")
# Binary search for the smallest zipped_size that gets an unzipped_size greater
# than 2^64-1 (actually 2^64 because of floating-point imprecision).
zipped_size_opt <- bsearch_fn(1*1024*1024*1024, NA, function(zipped_size) {
	params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size)
	unzipped_size <- QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)
	cat(sprintf("%.f %.5f\n", zipped_size, log(unzipped_size, 2)))
	unzipped_size >= 2^64
})
params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size_opt)
params
print(c("zipped size", QUOTED_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))

cat("\n\noptimize zbxxl.zip with extra-field quoting\n")
# Binary search for the smallest zipped_size that gets an unzipped_size greater
# than 2^64-1 (actually 2^64 because of floating-point imprecision).
zipped_size_opt <- bsearch_fn(1*1024*1024*1024, NA, function(zipped_size) {
	params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size, extra_quoting=TRUE)
	unzipped_size <- QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)
	cat(sprintf("%.f %.5f\n", zipped_size, log(unzipped_size, 2)))
	unzipped_size >= 2^64
})
params <- QUOTED_DEFLATE_64_optimize_for_zipped_size(zipped_size_opt, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_64_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_DEFLATE_64_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))

QUOTED_DEFLATE_largest_file <- function(compressed_size, num_files, extra_quoting=FALSE) {
	num_quot_ext <- if (extra_quoting) cmin(num_files - 1, max_num_quot_ext) else 0
	num_quot_def <- cmax(num_files - 1 - num_quot_ext, 0)
	DEFLATE_uncompressed_size_given_compressed_size(compressed_size) + lfh*num_quot_def + sum_filename_lengths(num_files) - sum_filename_lengths(num_files-num_quot_def)
}

QUOTED_DEFLATE_needs_zip64 <- function(compressed_size, num_files, extra_quoting=FALSE) {
	(num_files > 0xfffe) | (QUOTED_DEFLATE_largest_file(compressed_size, num_files, extra_quoting) > 0xfffffffe)
}

QUOTED_BZIP2_largest_file <- function(compressed_size, num_files, extra_quoting=FALSE) {
	if (!extra_quoting)
		stop()
	# no file size expansion with bzip2, because of only extra-field quoting
	BZIP2_uncompressed_size_given_compressed_size(compressed_size)
}

QUOTED_BZIP2_needs_zip64 <- function(compressed_size, num_files, extra_quoting=FALSE) {
	QUOTED_BZIP2_largest_file(compressed_size, num_files, extra_quoting) > 0xfffffffe
}

cat("\n\nsmallest DEFLATE zipped_size that requires Zip64\n")
zipped_size_opt <- bsearch_fn(1*1024*1024, NA, function(zipped_size) {
	params <- QUOTED_DEFLATE_optimize_for_zipped_size(zipped_size)
	QUOTED_DEFLATE_needs_zip64(params$compressed_size, params$num_files)
})
params <- QUOTED_DEFLATE_optimize_for_zipped_size(zipped_size_opt)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_compressed_size(params$compressed_size, params$num_files)))
QUOTED_DEFLATE_largest_file(params$compressed_size, params$num_files)

cat("\n\nsmallest DEFLATE zipped_size with extra-field quoting that requires Zip64\n")
zipped_size_opt <- bsearch_fn(1*1024*1024, NA, function(zipped_size) {
	params <- QUOTED_DEFLATE_optimize_for_zipped_size(zipped_size, extra_quoting=TRUE)
	QUOTED_DEFLATE_needs_zip64(params$compressed_size, params$num_files, extra_quoting=TRUE)
})
params <- QUOTED_DEFLATE_optimize_for_zipped_size(zipped_size_opt, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_DEFLATE_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
QUOTED_DEFLATE_largest_file(params$compressed_size, params$num_files, extra_quoting=TRUE)

cat("\n\nsmallest bzip2 zipped_size with extra-field quoting that requires Zip64\n")
zipped_size_opt <- bsearch_fn(1*1024, NA, function(max_zipped_size) {
	params <- QUOTED_BZIP2_optimize_for_max_zipped_size(max_zipped_size, extra_quoting=TRUE)
	QUOTED_BZIP2_needs_zip64(params$compressed_size, params$num_files, extra_quoting=TRUE)
})
params <- QUOTED_BZIP2_optimize_for_max_zipped_size(zipped_size_opt, extra_quoting=TRUE)
params
print(c("zipped size", QUOTED_zipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
print(c("unzipped size", QUOTED_BZIP2_unzipped_size_given_compressed_size(params$compressed_size, params$num_files, extra_quoting=TRUE)))
QUOTED_BZIP2_largest_file(params$compressed_size, params$num_files, extra_quoting=TRUE)