aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rwxr-xr-xplayground/calculate.sh2
-rw-r--r--playground/gdb-calculate.gdb5
-rwxr-xr-xplayground/gdb-calculate.sh20
-rw-r--r--playground/params.json31
-rw-r--r--src_c/opcut.c62
-rw-r--r--src_doit/c.py5
-rw-r--r--src_js/states.js2
-rw-r--r--src_py/opcut/libopcut.py2
-rw-r--r--src_py/opcut/main.py2
9 files changed, 94 insertions, 37 deletions
diff --git a/playground/calculate.sh b/playground/calculate.sh
index 9368a6d..9aa6a49 100755
--- a/playground/calculate.sh
+++ b/playground/calculate.sh
@@ -3,6 +3,6 @@
. $(dirname -- "$0")/env.sh
exec $PYTHON -m opcut calculate \
- --method forward_greedy \
+ --method forward_greedy_native \
--output $RUN_PATH/result.json \
$RUN_PATH/params.json
diff --git a/playground/gdb-calculate.gdb b/playground/gdb-calculate.gdb
new file mode 100644
index 0000000..952559f
--- /dev/null
+++ b/playground/gdb-calculate.gdb
@@ -0,0 +1,5 @@
+set breakpoint pending on
+
+# break src_c/opcut.c:opcut_calculate
+
+run
diff --git a/playground/gdb-calculate.sh b/playground/gdb-calculate.sh
new file mode 100755
index 0000000..f2bf64b
--- /dev/null
+++ b/playground/gdb-calculate.sh
@@ -0,0 +1,20 @@
+#!/bin/sh
+
+set -e
+
+. $(dirname -- "$0")/env.sh
+
+PYTHON_BIN="$($PYTHON -c "import sys; print(sys.executable)")"
+
+
+cd $ROOT_PATH
+doit clean_all
+doit json_schema_repo c
+
+cd $RUN_PATH
+exec gdb --directory $ROOT_PATH \
+ --command $RUN_PATH/gdb-calculate.gdb \
+ --args $PYTHON_BIN -m opcut calculate \
+ --method forward_greedy_native \
+ --output $RUN_PATH/result.json \
+ $RUN_PATH/params.json
diff --git a/playground/params.json b/playground/params.json
index 789505c..5aff8ca 100644
--- a/playground/params.json
+++ b/playground/params.json
@@ -1,5 +1,6 @@
{
"cut_width": 1,
+ "min_initial_usage": true,
"panels": {
"p1": {
"width": 50,
@@ -8,9 +9,39 @@
},
"items": {
"i1": {
+ "width": 1,
+ "height": 5,
+ "can_rotate": true
+ },
+ "i1_1": {
+ "width": 1,
+ "height": 5,
+ "can_rotate": true
+ },
+ "i1_2": {
+ "width": 1,
+ "height": 5,
+ "can_rotate": true
+ },
+ "i1_3": {
+ "width": 1,
+ "height": 5,
+ "can_rotate": true
+ },
+ "i1_4": {
+ "width": 1,
+ "height": 5,
+ "can_rotate": true
+ },
+ "i2": {
"width": 5,
"height": 5,
"can_rotate": true
+ },
+ "i3": {
+ "width": 10,
+ "height": 10,
+ "can_rotate": true
}
}
}
diff --git a/src_c/opcut.c b/src_c/opcut.c
index 9946d1c..494ef6d 100644
--- a/src_c/opcut.c
+++ b/src_c/opcut.c
@@ -4,6 +4,8 @@
#define PAGE_SIZE 4096
#define FITNESS_K 0.03
+typedef double (*sort_compare_fn)(opcut_params_t *params, size_t id1,
+ size_t id2);
typedef struct mem_header_t {
struct mem_header_t *next;
@@ -137,51 +139,39 @@ static inline void swap_ids(size_t *ids, size_t pos1, size_t pos2) {
}
-static size_t partition_panel_ids(opcut_params_t *params, size_t *panel_ids,
- size_t start, size_t stop) {
+static size_t partition_ids(opcut_params_t *params, sort_compare_fn cmp,
+ size_t *ids, size_t start, size_t stop) {
ssize_t pivot = start - 1;
for (size_t i = start; i < stop; ++i)
- if (params->panels[panel_ids[i]].area >=
- params->panels[panel_ids[stop]].area)
- swap_ids(panel_ids, ++pivot, i);
+ if (cmp(params, ids[i], ids[stop]) >= 0)
+ swap_ids(ids, ++pivot, i);
pivot += 1;
- swap_ids(panel_ids, pivot, stop);
+ swap_ids(ids, pivot, stop);
return pivot;
}
-static void sort_panel_ids(opcut_params_t *params, size_t *panel_ids,
- size_t start, size_t stop) {
+static void sort_ids(opcut_params_t *params, sort_compare_fn cmp, size_t *ids,
+ size_t start, size_t stop) {
if (start >= stop)
return;
- size_t pivot = partition_panel_ids(params, panel_ids, start, stop);
- sort_panel_ids(params, panel_ids, start, pivot - 1);
- sort_panel_ids(params, panel_ids, pivot + 1, stop);
+ size_t pivot = partition_ids(params, cmp, ids, start, stop);
+ if (pivot)
+ sort_ids(params, cmp, ids, start, pivot - 1);
+ sort_ids(params, cmp, ids, pivot + 1, stop);
}
-static size_t partition_item_ids(opcut_params_t *params, size_t *item_ids,
- size_t start, size_t stop) {
- ssize_t pivot = start - 1;
- for (size_t i = start; i < stop; ++i)
- if (params->items[item_ids[i]].area >=
- params->items[item_ids[stop]].area)
- swap_ids(item_ids, ++pivot, i);
- pivot += 1;
- swap_ids(item_ids, pivot, stop);
- return pivot;
+static double compare_panels(opcut_params_t *params, size_t panel_id1,
+ size_t panel_id2) {
+ return params->panels[panel_id1].area - params->panels[panel_id2].area;
}
-static void sort_item_ids(opcut_params_t *params, size_t *item_ids,
- size_t start, size_t stop) {
- if (start >= stop)
- return;
-
- size_t pivot = partition_item_ids(params, item_ids, start, stop);
- sort_item_ids(params, item_ids, start, pivot - 1);
- sort_item_ids(params, item_ids, pivot + 1, stop);
+static double compare_items(opcut_params_t *params, size_t item_id1,
+ size_t item_id2) {
+ return params->items[item_id1].area - params->items[item_id2].area;
}
@@ -197,7 +187,7 @@ static size_t *create_initial_item_ids(opcut_allocator_t *a,
for (size_t item_id = 0; item_id < params->items_len; ++item_id)
item_ids[item_id] = item_id;
- sort_item_ids(params, item_ids, 0, params->items_len - 1);
+ sort_ids(params, compare_items, item_ids, 0, params->items_len - 1);
return item_ids;
}
@@ -215,7 +205,7 @@ static opcut_unused_t *create_initial_unused(opcut_allocator_t *a,
for (size_t panel_id = 0; panel_id < params->panels_len; ++panel_id)
panel_ids[panel_id] = panel_id;
- sort_panel_ids(params, panel_ids, 0, params->panels_len - 1);
+ sort_ids(params, compare_panels, panel_ids, 0, params->panels_len - 1);
opcut_unused_t *unused = NULL;
for (size_t i = 0; i < params->panels_len; ++i) {
@@ -245,7 +235,7 @@ static opcut_unused_t *create_initial_unused(opcut_allocator_t *a,
}
-static inline int compare_fitness(fitness_t *f1, fitness_t *f2) {
+static inline double compare_fitness(fitness_t *f1, fitness_t *f2) {
if (f1->unused_initial_count == f2->unused_initial_count)
return f1->fitness - f2->fitness;
return f1->unused_initial_count - f2->unused_initial_count;
@@ -367,6 +357,14 @@ static int cut_item_from_unused(opcut_allocator_t *a, opcut_params_t *params,
result->unused = new_unused;
}
+ if (result->unused && result->unused->next &&
+ result->unused->area > result->unused->next->area) {
+ opcut_unused_t *temp = result->unused->next;
+ result->unused->next = temp->next;
+ temp->next = result->unused;
+ result->unused = temp;
+ }
+
return OPCUT_SUCCESS;
}
diff --git a/src_doit/c.py b/src_doit/c.py
index bd9fd74..36257f6 100644
--- a/src_doit/c.py
+++ b/src_doit/c.py
@@ -21,10 +21,13 @@ platforms = [common.local_platform]
if common.local_platform == common.Platform.LINUX_X86_64:
platforms.append(common.Platform.WINDOWS_AMD64)
+cc_flags = ['-fPIC', '-O2']
+# cc_flags = ['-fPIC', '-O0', '-ggdb']
+
builds = [CBuild(src_paths=[*src_c_dir.rglob('*.c')],
build_dir=build_c_dir / platform.name.lower(),
platform=platform,
- cc_flags=['-fPIC', '-O2'])
+ cc_flags=cc_flags)
for platform in platforms]
lib_paths = [src_py_dir / (f'opcut/_libopcut{get_lib_suffix(platform)}')
diff --git a/src_js/states.js b/src_js/states.js
index bf3584e..bc50eb3 100644
--- a/src_js/states.js
+++ b/src_js/states.js
@@ -3,7 +3,7 @@ export const main = {
form: {
method: 'forward_greedy',
cut_width: 0.3,
- min_initial_usage: false,
+ min_initial_usage: true,
panels: [],
items: []
},
diff --git a/src_py/opcut/libopcut.py b/src_py/opcut/libopcut.py
index b5531aa..d5120cd 100644
--- a/src_py/opcut/libopcut.py
+++ b/src_py/opcut/libopcut.py
@@ -31,7 +31,7 @@ def calculate(method: common.Method,
raise common.UnresolvableError()
if ret != _lib.OPCUT_SUCCESS:
- raise Exception()
+ raise Exception("calculation error")
used = list(_decode_used(params, native_used))
unused = list(_decode_unused(params, native_unused))
diff --git a/src_py/opcut/main.py b/src_py/opcut/main.py
index 958e135..58b3060 100644
--- a/src_py/opcut/main.py
+++ b/src_py/opcut/main.py
@@ -41,7 +41,7 @@ def create_argument_parser() -> argparse.ArgumentParser:
'--output', metavar='PATH', type=Path, default=Path('-'),
help=f"output result file path or - for stdout ({result_schema_id})")
calculate.add_argument(
- 'params', type=Path, default=Path('-'),
+ 'params', type=Path, default=Path('-'), nargs='?',
help=f"input params file path or - for stdin ({params_schema_id})")
generate = subparsers.add_parser('generate')
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-02-11 16:33:12 +0000