Add wimlib_get_compressor_needed_memory()
authorEric Biggers <ebiggers3@gmail.com>
Thu, 2 Jan 2014 06:28:48 +0000 (00:28 -0600)
committerEric Biggers <ebiggers3@gmail.com>
Thu, 2 Jan 2014 06:28:48 +0000 (00:28 -0600)
include/wimlib.h
include/wimlib/compressor_ops.h
include/wimlib/lz_optimal.h
include/wimlib/lz_sarray.h
src/compress.c
src/compress_parallel.c
src/lz_sarray.c
src/lzms-compress.c
src/lzx-compress.c
src/xpress-compress.c

index 372bb76..129a6c5 100644 (file)
@@ -4118,6 +4118,8 @@ struct wimlib_decompressor;
  *
  * @retval ::WIMLIB_ERR_INVALID_COMPRESSION_TYPE
  *     @p ctype was not a supported compression type.
+ * @retval ::WIMLIB_ERR_INVALID_PARAM
+ *     @p params were invalid.
  * @retval ::WIMLIB_ERR_NOMEM
  *     Not enough memory to duplicate the parameters (perhaps @c params->size
  *     was invalid).
@@ -4127,6 +4129,18 @@ wimlib_set_default_compressor_params(enum wimlib_compression_type ctype,
                                     const struct wimlib_compressor_params_header *params);
 
 /**
+ * Returns the approximate number of bytes needed to allocate a compressor with
+ * wimlib_create_compressor() for the specified compression type, block size,
+ * and parameters.  @p params may be @c NULL, in which case the current default
+ * parameters for @p ctype are used.  Returns 0 if the compression type or
+ * parameters are invalid.
+ */
+extern uint64_t
+wimlib_get_compressor_needed_memory(enum wimlib_compression_type ctype,
+                                   size_t max_block_size,
+                                   const struct wimlib_compressor_params_header *params);
+
+/**
  * Allocate a compressor for the specified compression type using the specified
  * parameters.
  *
index 4c36bb3..e172e56 100644 (file)
@@ -7,12 +7,17 @@
 #ifndef _WIMLIB_COMPRESSOR_OPS_H
 #define _WIMLIB_COMPRESSOR_OPS_H
 
-#include <stddef.h>
+#include <wimlib/types.h>
 
 struct compressor_ops {
 
+       bool (*params_valid)(const struct wimlib_compressor_params_header *params);
+
+       u64 (*get_needed_memory)(size_t max_block_size,
+                                const struct wimlib_compressor_params_header *params);
+
        int (*create_compressor)(size_t max_block_size,
-                                const struct wimlib_compressor_params_header *extra_params,
+                                const struct wimlib_compressor_params_header *params,
                                 void **private_ret);
 
        size_t (*compress)(const void *uncompressed_data,
index 32bbb8b..4e78109 100644 (file)
@@ -145,6 +145,16 @@ lz_match_chooser_init(struct lz_match_chooser *mc,
        return true;
 }
 
+static inline u64
+lz_match_chooser_get_needed_memory(input_idx_t array_space,
+                                  input_idx_t nice_len,
+                                  input_idx_t max_match_len)
+{
+       input_idx_t extra_len = min(nice_len, max_match_len);
+       return ((u64)(array_space + extra_len) *
+               sizeof(((struct lz_match_chooser*)0)->optimum[0]));
+}
+
 /* Free memory allocated in lz_match_chooser_init().  */
 static void
 lz_match_chooser_destroy(struct lz_match_chooser *mc)
index 74f77a1..e51f59d 100644 (file)
@@ -143,6 +143,9 @@ lz_sarray_init(struct lz_sarray *mf,
               u32 max_matches_to_consider,
               u32 max_matches_to_return);
 
+extern u64
+lz_sarray_get_needed_memory(input_idx_t max_window_size);
+
 extern void
 lz_sarray_destroy(struct lz_sarray *mf);
 
index a3c95b0..9884a7c 100644 (file)
@@ -64,6 +64,11 @@ wimlib_set_default_compressor_params(enum wimlib_compression_type ctype,
        if (!compressor_ctype_valid(ctype))
                return WIMLIB_ERR_INVALID_COMPRESSION_TYPE;
 
+       if (params != NULL &&
+           compressor_ops[ctype]->params_valid != NULL &&
+           !compressor_ops[ctype]->params_valid(params))
+               return WIMLIB_ERR_INVALID_PARAM;
+
        dup = NULL;
        if (params) {
                dup = memdup(params, params->size);
@@ -85,6 +90,33 @@ cleanup_compressor_params(void)
        }
 }
 
+WIMLIBAPI u64
+wimlib_get_compressor_needed_memory(enum wimlib_compression_type ctype,
+                                   size_t max_block_size,
+                                   const struct wimlib_compressor_params_header *extra_params)
+{
+       const struct compressor_ops *ops;
+       const struct wimlib_compressor_params_header *params;
+
+       if (!compressor_ctype_valid(ctype))
+               return 0;
+
+       ops = compressor_ops[ctype];
+       if (ops->get_needed_memory == NULL)
+               return 0;
+
+       if (extra_params) {
+               params = extra_params;
+               if (ops->params_valid && !ops->params_valid(params))
+                       return 0;
+       } else {
+               params = compressor_default_params[ctype];
+       }
+
+       return ops->get_needed_memory(max_block_size, params);
+}
+
+
 WIMLIBAPI int
 wimlib_create_compressor(enum wimlib_compression_type ctype,
                         size_t max_block_size,
@@ -108,10 +140,15 @@ wimlib_create_compressor(enum wimlib_compression_type ctype,
                const struct wimlib_compressor_params_header *params;
                int ret;
 
-               if (extra_params)
+               if (extra_params) {
                        params = extra_params;
-               else
+                       if (c->ops->params_valid && !c->ops->params_valid(params)) {
+                               FREE(c);
+                               return WIMLIB_ERR_INVALID_PARAM;
+                       }
+               } else {
                        params = compressor_default_params[ctype];
+               }
                ret = c->ops->create_compressor(max_block_size,
                                                params, &c->private);
                if (ret) {
index 6cd306c..376e59d 100644 (file)
@@ -438,8 +438,11 @@ new_parallel_chunk_compressor(int out_ctype, u32 out_chunk_size,
                        (u64)msgs_per_thread *
                        (u64)num_threads *
                        (u64)out_chunk_size
+                       + out_chunk_size
                        + 1000000
-                       + (out_chunk_size * num_threads * 4);
+                       + num_threads * wimlib_get_compressor_needed_memory(out_ctype,
+                                                                           out_chunk_size,
+                                                                           NULL);
                if (approx_mem_required <= max_memory)
                        break;
 
index ffffcd1..b880f9c 100644 (file)
@@ -377,6 +377,12 @@ lz_sarray_init(struct lz_sarray *mf,
        return true;
 }
 
+u64
+lz_sarray_get_needed_memory(input_idx_t max_window_size)
+{
+       return (u64)6 * sizeof(input_idx_t) * max_window_size;
+}
+
 /*
  * Prepare the suffix array match-finder to scan the specified window for
  * matches.
index 31648f0..72aef31 100644 (file)
@@ -1226,7 +1226,7 @@ lzms_free_compressor(void *_ctx)
        }
 }
 
-static const struct wimlib_lzms_compressor_params default_params = {
+static const struct wimlib_lzms_compressor_params lzms_default = {
        .hdr = sizeof(struct wimlib_lzms_compressor_params),
        .min_match_length = 2,
        .max_match_length = UINT32_MAX,
@@ -1236,37 +1236,36 @@ static const struct wimlib_lzms_compressor_params default_params = {
        .optim_array_length = 1024,
 };
 
+static const struct wimlib_lzms_compressor_params *
+lzms_get_params(const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzms_compressor_params *params =
+               (const struct wimlib_lzms_compressor_params*)_params;
+
+       if (params == NULL)
+               params = &lzms_default;
+
+       return params;
+}
+
 static int
 lzms_create_compressor(size_t max_block_size,
                       const struct wimlib_compressor_params_header *_params,
                       void **ctx_ret)
 {
        struct lzms_compressor *ctx;
-       const struct wimlib_lzms_compressor_params *params;
+       const struct wimlib_lzms_compressor_params *params = lzms_get_params(_params);
 
        if (max_block_size == 0 || max_block_size >= INT32_MAX) {
                LZMS_DEBUG("Invalid max_block_size (%u)", max_block_size);
                return WIMLIB_ERR_INVALID_PARAM;
        }
 
-       if (_params)
-               params = (const struct wimlib_lzms_compressor_params*)_params;
-       else
-               params = &default_params;
-
-       if (params->max_match_length < params->min_match_length ||
-           params->min_match_length < 2 ||
-           params->optim_array_length == 0 ||
-           min(params->max_match_length, params->nice_match_length) > 65536) {
-               LZMS_DEBUG("Invalid compression parameter!");
-               return WIMLIB_ERR_INVALID_PARAM;
-       }
-
        ctx = CALLOC(1, sizeof(struct lzms_compressor));
        if (ctx == NULL)
                goto oom;
 
-       ctx->window = MALLOC(max_block_size + 8);
+       ctx->window = MALLOC(max_block_size);
        if (ctx->window == NULL)
                goto oom;
 
@@ -1312,7 +1311,46 @@ oom:
        return WIMLIB_ERR_NOMEM;
 }
 
+static u64
+lzms_get_needed_memory(size_t max_block_size,
+                      const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzms_compressor_params *params = lzms_get_params(_params);
+
+       u64 size = 0;
+
+       size += max_block_size;
+       size += sizeof(struct lzms_compressor);
+       size += lz_sarray_get_needed_memory(max_block_size);
+       size += lz_match_chooser_get_needed_memory(params->optim_array_length,
+                                                  params->nice_match_length,
+                                                  params->max_match_length);
+       size += min(params->max_match_length -
+                   params->min_match_length + 1,
+                   params->max_matches_per_pos) *
+               sizeof(((struct lzms_compressor*)0)->matches[0]);
+       return size;
+}
+
+static bool
+lzms_params_valid(const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzms_compressor_params *params =
+               (const struct wimlib_lzms_compressor_params*)_params;
+
+       if (params->hdr.size != sizeof(*params) ||
+           params->max_match_length < params->min_match_length ||
+           params->min_match_length < 2 ||
+           params->optim_array_length == 0 ||
+           min(params->max_match_length, params->nice_match_length) > 65536)
+               return false;
+
+       return true;
+}
+
 const struct compressor_ops lzms_compressor_ops = {
+       .params_valid       = lzms_params_valid,
+       .get_needed_memory  = lzms_get_needed_memory,
        .create_compressor  = lzms_create_compressor,
        .compress           = lzms_compress,
        .free_compressor    = lzms_free_compressor,
index 2cce444..0c891a7 100644 (file)
@@ -1577,53 +1577,6 @@ lzx_compress(const void *uncompressed_data, size_t uncompressed_size,
        return compressed_size;
 }
 
-static bool
-lzx_params_valid(const struct wimlib_lzx_compressor_params *params)
-{
-       /* Validate parameters.  */
-       if (params->hdr.size != sizeof(struct wimlib_lzx_compressor_params)) {
-               LZX_DEBUG("Invalid parameter structure size!");
-               return false;
-       }
-
-       if (params->algorithm != WIMLIB_LZX_ALGORITHM_SLOW &&
-           params->algorithm != WIMLIB_LZX_ALGORITHM_FAST)
-       {
-               LZX_DEBUG("Invalid algorithm.");
-               return false;
-       }
-
-       if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
-               if (params->alg_params.slow.num_optim_passes < 1)
-               {
-                       LZX_DEBUG("Invalid number of optimization passes!");
-                       return false;
-               }
-
-               if (params->alg_params.slow.main_nostat_cost < 1 ||
-                   params->alg_params.slow.main_nostat_cost > 16)
-               {
-                       LZX_DEBUG("Invalid main_nostat_cost!");
-                       return false;
-               }
-
-               if (params->alg_params.slow.len_nostat_cost < 1 ||
-                   params->alg_params.slow.len_nostat_cost > 16)
-               {
-                       LZX_DEBUG("Invalid len_nostat_cost!");
-                       return false;
-               }
-
-               if (params->alg_params.slow.aligned_nostat_cost < 1 ||
-                   params->alg_params.slow.aligned_nostat_cost > 8)
-               {
-                       LZX_DEBUG("Invalid aligned_nostat_cost!");
-                       return false;
-               }
-       }
-       return true;
-}
-
 static void
 lzx_free_compressor(void *_ctx)
 {
@@ -1641,13 +1594,63 @@ lzx_free_compressor(void *_ctx)
        }
 }
 
+static const struct wimlib_lzx_compressor_params lzx_fast_default = {
+       .hdr = {
+               .size = sizeof(struct wimlib_lzx_compressor_params),
+       },
+       .algorithm = WIMLIB_LZX_ALGORITHM_FAST,
+       .use_defaults = 0,
+       .alg_params = {
+               .fast = {
+               },
+       },
+};
+static const struct wimlib_lzx_compressor_params lzx_slow_default = {
+       .hdr = {
+               .size = sizeof(struct wimlib_lzx_compressor_params),
+       },
+       .algorithm = WIMLIB_LZX_ALGORITHM_SLOW,
+       .use_defaults = 0,
+       .alg_params = {
+               .slow = {
+                       .use_len2_matches = 1,
+                       .nice_match_length = 32,
+                       .num_optim_passes = 2,
+                       .max_search_depth = 50,
+                       .max_matches_per_pos = 3,
+                       .main_nostat_cost = 15,
+                       .len_nostat_cost = 15,
+                       .aligned_nostat_cost = 7,
+               },
+       },
+};
+
+static const struct wimlib_lzx_compressor_params *
+lzx_get_params(const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzx_compressor_params *params =
+               (const struct wimlib_lzx_compressor_params*)_params;
+
+       if (params == NULL) {
+               LZX_DEBUG("Using default algorithm and parameters.");
+               params = &lzx_slow_default;
+       } else {
+               if (params->use_defaults) {
+                       if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW)
+                               params = &lzx_slow_default;
+                       else
+                               params = &lzx_fast_default;
+               }
+       }
+       return params;
+}
+
 static int
 lzx_create_compressor(size_t window_size,
                      const struct wimlib_compressor_params_header *_params,
                      void **ctx_ret)
 {
-       const struct wimlib_lzx_compressor_params *params =
-               (const struct wimlib_lzx_compressor_params*)_params;
+       const struct wimlib_lzx_compressor_params *params = lzx_get_params(_params);
        struct lzx_compressor *ctx;
 
        LZX_DEBUG("Allocating LZX context...");
@@ -1655,52 +1658,6 @@ lzx_create_compressor(size_t window_size,
        if (!lzx_window_size_valid(window_size))
                return WIMLIB_ERR_INVALID_PARAM;
 
-       static const struct wimlib_lzx_compressor_params fast_default = {
-               .hdr = {
-                       .size = sizeof(struct wimlib_lzx_compressor_params),
-               },
-               .algorithm = WIMLIB_LZX_ALGORITHM_FAST,
-               .use_defaults = 0,
-               .alg_params = {
-                       .fast = {
-                       },
-               },
-       };
-       static const struct wimlib_lzx_compressor_params slow_default = {
-               .hdr = {
-                       .size = sizeof(struct wimlib_lzx_compressor_params),
-               },
-               .algorithm = WIMLIB_LZX_ALGORITHM_SLOW,
-               .use_defaults = 0,
-               .alg_params = {
-                       .slow = {
-                               .use_len2_matches = 1,
-                               .nice_match_length = 32,
-                               .num_optim_passes = 2,
-                               .max_search_depth = 50,
-                               .max_matches_per_pos = 3,
-                               .main_nostat_cost = 15,
-                               .len_nostat_cost = 15,
-                               .aligned_nostat_cost = 7,
-                       },
-               },
-       };
-
-       if (params) {
-               if (!lzx_params_valid(params))
-                       return WIMLIB_ERR_INVALID_PARAM;
-       } else {
-               LZX_DEBUG("Using default algorithm and parameters.");
-               params = &slow_default;
-       }
-
-       if (params->use_defaults) {
-               if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW)
-                       params = &slow_default;
-               else
-                       params = &fast_default;
-       }
-
        LZX_DEBUG("Allocating memory.");
 
        ctx = CALLOC(1, sizeof(struct lzx_compressor));
@@ -1776,7 +1733,96 @@ oom:
        return WIMLIB_ERR_NOMEM;
 }
 
+static u64
+lzx_get_needed_memory(size_t max_block_size,
+                     const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzx_compressor_params *params = lzx_get_params(_params);
+
+       u64 size = 0;
+
+       size += sizeof(struct lzx_compressor);
+
+       size += max_block_size + 12;
+
+       size += DIV_ROUND_UP(max_block_size, LZX_DIV_BLOCK_SIZE) *
+               sizeof(((struct lzx_compressor*)0)->block_specs[0]);
+
+       if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW) {
+               size += max_block_size * sizeof(((struct lzx_compressor*)0)->chosen_matches[0]);
+               size += lz_sarray_get_needed_memory(max_block_size);
+               size += lz_match_chooser_get_needed_memory(LZX_OPTIM_ARRAY_SIZE,
+                                                          params->alg_params.slow.nice_match_length,
+                                                          LZX_MAX_MATCH_LEN);
+               u32 cache_per_pos;
+
+               cache_per_pos = params->alg_params.slow.max_matches_per_pos;
+               if (cache_per_pos > LZX_MAX_CACHE_PER_POS)
+                       cache_per_pos = LZX_MAX_CACHE_PER_POS;
+
+               size += max_block_size * (cache_per_pos + 1) *
+                       sizeof(((struct lzx_compressor*)0)->cached_matches[0]);
+       } else {
+               size += max_block_size * sizeof(((struct lzx_compressor*)0)->prev_tab[0]);
+       }
+       return size;
+}
+
+static bool
+lzx_params_valid(const struct wimlib_compressor_params_header *_params)
+{
+       const struct wimlib_lzx_compressor_params *params =
+               (const struct wimlib_lzx_compressor_params*)_params;
+
+       if (params->hdr.size != sizeof(struct wimlib_lzx_compressor_params)) {
+               LZX_DEBUG("Invalid parameter structure size!");
+               return false;
+       }
+
+       if (params->algorithm != WIMLIB_LZX_ALGORITHM_SLOW &&
+           params->algorithm != WIMLIB_LZX_ALGORITHM_FAST)
+       {
+               LZX_DEBUG("Invalid algorithm.");
+               return false;
+       }
+
+       if (params->algorithm == WIMLIB_LZX_ALGORITHM_SLOW &&
+           !params->use_defaults)
+       {
+               if (params->alg_params.slow.num_optim_passes < 1)
+               {
+                       LZX_DEBUG("Invalid number of optimization passes!");
+                       return false;
+               }
+
+               if (params->alg_params.slow.main_nostat_cost < 1 ||
+                   params->alg_params.slow.main_nostat_cost > 16)
+               {
+                       LZX_DEBUG("Invalid main_nostat_cost!");
+                       return false;
+               }
+
+               if (params->alg_params.slow.len_nostat_cost < 1 ||
+                   params->alg_params.slow.len_nostat_cost > 16)
+               {
+                       LZX_DEBUG("Invalid len_nostat_cost!");
+                       return false;
+               }
+
+               if (params->alg_params.slow.aligned_nostat_cost < 1 ||
+                   params->alg_params.slow.aligned_nostat_cost > 8)
+               {
+                       LZX_DEBUG("Invalid aligned_nostat_cost!");
+                       return false;
+               }
+       }
+       return true;
+}
+
+
 const struct compressor_ops lzx_compressor_ops = {
+       .params_valid       = lzx_params_valid,
+       .get_needed_memory  = lzx_get_needed_memory,
        .create_compressor  = lzx_create_compressor,
        .compress           = lzx_compress,
        .free_compressor    = lzx_free_compressor,
index b163887..175534c 100644 (file)
@@ -314,7 +314,22 @@ oom:
        return WIMLIB_ERR_NOMEM;
 }
 
+static u64
+xpress_get_needed_memory(size_t max_window_size,
+                        const struct wimlib_compressor_params_header *params)
+{
+       u64 size = 0;
+
+       size += sizeof(struct xpress_compressor);
+       size += max_window_size + 8;
+       size += max_window_size * sizeof(((struct xpress_compressor*)0)->matches[0]);
+       size += max_window_size * sizeof(((struct xpress_compressor*)0)->prev_tab[0]);
+
+       return size;
+}
+
 const struct compressor_ops xpress_compressor_ops = {
+       .get_needed_memory  = xpress_get_needed_memory,
        .create_compressor  = xpress_create_compressor,
        .compress           = xpress_compress,
        .free_compressor    = xpress_free_compressor,