Warning: this also swaps the arguments of the old rz_bv_append() to be
consistend with the new inplace variant.
The reason why the inplace function has the low as the first operand is
that it can be more efficient to append to an existing vector inplace
than to prepend to it. Then, the first argument is being used as the
in-out one in all other inplace functions.
- Introduced md1img.h and md1img.c for parsing MediaTek md1img container format.
- Implemented mtk.h and mtk.c for parsing MediaTek GFH firmware images (md1rom).
- Added plugin support for md1img and mtk formats in bin_md1img.c and bin_mtk.c.
- Updated meson.build to include new source files and plugins.
- Enhanced RzBuffer utility with LZMA alone decompression support.
---------
Co-authored-by: Giovanni <561184+wargio@users.noreply.github.com>
* util/vector: hoist quicksort scratch buffers out of the recursion
vector_quick_sort allocated its two element-sized scratch buffers (t and
pivot) with malloc/free on every recursive call. For a vector of n elements
the sort makes O(n) recursive calls, i.e. O(n) malloc/free pairs purely for
scratch space, and each call could also fail half-way through the sort.
Split the function into a small entry point that allocates the two buffers
once and a recursive worker that receives them as scratch. The buffers are
reused across the whole recursion (each partition step finishes using them
before recursing, and the recursion is sequential, so sharing one pair is
safe). Small elements -- the common case, including every RzPVector-backed
sort -- use stack buffers and allocate nothing at all; only elements larger
than 256 bytes fall back to a single heap allocation for the whole sort.
The element movement and rand()-based pivot selection are unchanged, so the
result is identical for any input (verified byte-for-byte against the previous
implementation for ascending and descending orders over many random arrays).
* util/vector: evaluate the comparator once per element in the quicksort
The partition loop tested the element against the pivot with two separate
calls to the comparator:
if ((cmp(VEC_INDEX(a, i), pivot, user) < 0 && !reverse) ||
(cmp(VEC_INDEX(a, i), pivot, user) > 0 && reverse)) {
Because cmp is an opaque function pointer the compiler cannot common up the
two calls, so depending on the result and the reverse flag the comparator was
invoked up to twice per element. Compute the result once into a local and test
that:
int c = cmp(VEC_INDEX(a, i), pivot, user);
if ((c < 0 && !reverse) || (c > 0 && reverse)) {
This halves comparator calls in the worst case and is a clear win whenever the
comparator is non-trivial (the common case for struct elements). Measured on a
shared host: ~12-14% faster for int sorting and ~30% faster with a moderately
expensive comparator. The ordering is unchanged (verified byte-for-byte).
* util/vector: simplify rz_pvector_remove_data index computation
The index of the located slot was computed as
size_t index = (el - (void **)vec->v.a) * sizeof(void **) / vec->v.elem_size;
For an RzPVector the element size is always sizeof(void *), so the
`* sizeof(void **) / vec->v.elem_size` factor is identically 1 and the pointer
difference `el - (void **)vec->v.a` already yields the index directly. Drop the
redundant scaling, which removes a multiply and a divide and makes the intent
clear. Behaviour is unchanged.
* test/unit: add RzVector sort and rz_pvector_remove_data regression tests
The existing sort tests only sort 4-5 small elements and there was no test for
rz_pvector_remove_data. Add coverage for the code paths exercised by the sort
changes and the remove_data cleanup:
- test_vector_sort_large sort 2000 heavily-duplicated ut32 values
ascending and descending, verifying the result
is ordered and a permutation of the input (vs a
reference qsort). Drives the recursion deeply
and the shared scratch buffers.
- test_vector_sort_large_elem sort 400 elements of 304 bytes each, taking the
heap-allocated scratch fallback, and check the
full payload (not just the key) stays consistent
through all the element moves.
- test_pvector_remove_data remove interior, first and last elements by
value while preserving order, and confirm
removing an absent value is a no-op.
All pass on both the previous and the optimized implementation (the sort and
remove_data changes are behaviour-preserving).
* test/bench: benchmark rz_vector_sort and rz_pvector_sort
bench_vector.c benchmarked only remove_at and swap. Add sort benchmarks so the
suite covers the functions touched by the sort optimizations and can be run
against the old and new librz for before/after numbers:
- rz_vector_sort over 4k ut64 with a cheap comparator
- rz_vector_sort over 4k ut64 with a deliberately expensive comparator
(shows the effect of evaluating the comparator once per element)
- rz_pvector_sort over 4k pointers (reference; pvector sort is unchanged)
Each iteration refills the buffer from an unsorted master copy via a single
memcpy before sorting; that overhead is identical across builds so the measured
delta reflects the sort.
---------
Co-authored-by: Anton Kochkov <anton.kochkov@gmail.com>
* Fix revert if adding a node failed.
* Reduce allocations by keeping only a single RzGraphEdge object per edge around.
* Add benchmark for graph deletion and addition of nodes/edges
* Use rz_pvector_remove_at_unsorted to save some runtime.
* Use realloc and memmove for matrix graphs on capacity increase.
* Add helper to determine memory usage.
* Add benchmark
* Revert matrix capacity extension to simple and jsut as fast loop.
* Missing type annotations
Consolidate the Unicode subscript notation used when rendering
bit-vector and float values (the subscript width on a bit-vector
constant, e.g. 0x2c followed by a subscript 8, and the format width
on a float, e.g. .f followed by a subscript 32) into one place, so
the RzIL Unicode exporter, the RzNum value printer, and the
RzNum->RzIL lift cannot drift apart.
RzUtil gains the single source of truth:
* rz_str_append_subscript() / rz_str_append_superscript() /
rz_str_subscript() render a number as Unicode subscript or
superscript digits;
* rz_bv_width_subscript() / rz_bv_as_unicode_string() build a
bit-vector's width subscript on top of the str helper;
* rz_float_format_subscript() renders a float format's width
subscript (16/32/64/80/128, with the decimal-format marker),
reusing the same digit renderer.
The RzIL Unicode exporter (il_export_string_unicode.c) is switched
fully onto these: every append_subscript() call site (bit-vector
constant width, cast length, memory indices) now goes through
rz_str_append_subscript(), and the hardcoded per-format subscript
macro is replaced by rz_float_format_subscript(). The exporter's
private subscript-digit table and ut32 glyph helper are removed, so
there is no longer a second, parallel implementation to keep in sync.
Signed-off-by: Anton Kochkov <anton.kochkov@gmail.com>
Co-authored-by: Anton Kochkov <anton.kochkov@gmail.com>
Detected with valgrind, some element assignments could memcpy with
identical addresses. This is usually a no-op in practice, but
theoretically undefined behavior.
* Add option to replace (geometric) invalid values with another value.
* Add geometric Mean and Std Dev to benchmarks.
* Add Doxygen documentation
* Add a README to the bench dir as intro.
empty_cond was never signalled and the termination depended only on
the timeout in rz_th_queue_close_when_empty() causing a re-check of
emptiness.
However, the rz_th_cond_timed_wait() implementation, which was used
there, was flawed because it expected a relative timeout but passed that
directly to pthread_cond_timedwait() which expected an absolute time
value, practically causing it to time out immediately. Depending on the
pthread_cond implementation, this possibly created a situation where the
mutex could never be acquired by another thread, effectively causing a
deadlock. This behavior was observed on Mac OS X 10.5 (ppc) when running
the test_core_bin test.
We solve this by not using a timeout at all and signalling the condition
variable for all waiting threads at the appropriate time.
* Add Welfords square of sums algorithm for variance and std deviation calculations.
* Add standard deviation to benchmarks
* Simplify Welford
* Add geometric mean and standard deviation to Welford Sums
* Add order ignoring remove_at version with better performance.
* Optimize rz_vector_swap by using stack memory for small elements.
* Add benchmark for rz_vector_swap
* Refactor del_edges to use RzGraphStatus.
* Refactor del_edge() to use RzGraphStatus.
* Refactor update_edge() to use RzGraphStatus.
* Refactor has_edge() to use RzGraphStatus.
* Refactor add_edge() to use RzGraphStatus.
* Fix leak of b
* Fix leak of xref list
* Fix leaks of analysis ops
* Address review comments
* Inlcude clean up
* Fix invalid free
* Add tests with node and edge data.
* Extend tests
* GRAPH: Add rz_graph_add_get_node() and refine API.
* GRAPH: Remove unused, and rename parameters.
* Improve doxygen.
* Implement rz_graph_del_edges()
* Rename rz_graph_node_get_hash_id() to rz_graph_node_get_hash_id() to make clear what identifier is returned.
* Simplify node identification.
Removes the option to have two sources of identifiers (node data or other identifier data).
Changes the API to use the hash id instead of a pointer to data.
* Fix type annotations.
* Remove duplicate function.
* Fix invalid asserts.
* Set flag if node was present.
* Grow by a factor of 1.25. Exponential growth quickly leads to OOM.
* Remove the edge index again to not remove reduce the main advantage of an adjacency matrix
* Refactor list based graph to use vectors instead of hash maps for edges.
* Fix heap-use-after-free
* Add an rz_graph_update_edge function.
* Add function to print graph as dot graph.
* Add warning about del_edges runtime.
* Refactor add_node to use RzGraphStatus.
* Refactor del_node to use RzGraphStatus.
* Use cast-macro to prevent ASAN issues.
* Add getter for vector capacity.
* Make rz_(p)vector_assign_at consistent in behavior.
* Document rz_vector_clear
* Move doxygen for rz_vector_flush to definition.
* Add rz_vector_purge for clearing, but capacity keeping.
* Rename flush -> take_array to signal ownership transfer.
* fix: memory leak rz_analysis_op_fini op->src
* fix: memory leak, replaced `rz_type_clone` with `rz_type_clone_shallow` to resolve the memory leak in `rz_type_free(type.callable)`
* fix: memory leak in try_create_var_global
* fix: memory leak in dwarf
* fix: remove redundant memset calls and add documentation for rz_type_clone_shallow
* Update librz/arch/op.c
Co-authored-by: Giovanni <561184+wargio@users.noreply.github.com>
* fix: set free and free_user to NULL in vector copy when item_cpy is not provided
---------
Co-authored-by: Giovanni <561184+wargio@users.noreply.github.com>
* perf: use binary search in `rz_vector_insert_sorted`
* Refactor bin_search_range to return exact insertion index
* Fix redundant `cmp` calls (reduced from 3x to 1x per iteration)
* Add null guard on `*i` pointer
* Return insertion point on miss to support `rz_vector_insert_sorted`
* Preserve O(log n) complexity without duplicating search logic
* Add first ring buffer implementation.
* Add likely and unlikely macros.
* Implement take and put
* Block writes to buffer if it is full.
* Make Is_open return bool and add unsafe fcn for is_empty
* Add ring buffer tests.
* Add blocking take() function to ring buffer.
* Add open() function to ring buffer
* Move ESIL into its own namespace
* Remove RzAnalysisEsilInterState from RzAnalysis
* More cleanup to split cil.c from ESIL code
* Rename RzAnalysisRzilTrace to RzAnalysisILTrace
* Fix various null-derefs.
* Remove rz_analysis_get/set_esil_inter_state
* Fix use after free and leaks
* Fix RZ_IPI declaration on public api for rz_pdb
* Fix RZ_IPI declaration on public api for jemalloc/glibc
* Fix RZ_IPI declaration on public api for rz_io
* Remove functions from public header for rz_panels
* Fix public functions not following rizin nomenclature in rz_graph
* Fix public functions not following rizin nomenclature in rz_rop
* move resolve_fcn_name into rz_analysis
* Fix public functions not following rizin nomenclature in rz_ascii_table
* Fix leak in rop code
* Rewrite parser for rop
* Add doxygen comment
* Basic implement of list based and matrix based graph
Add comments
Basic support for list and matrix based graph refactor
Add rz_graph_*_new node and edge API
Modify calling for rz graph edge data
Add dfs and visitor mode
Add new get nth neighbours
Add unit test and wrapper for get edges
Bug fixed and unit test
Solve TODO about better semantic of get nodes
Doc RZ_API and other functions, split impl to new files
[cannot build] remove old graph impl and rename new graph API
* Rewrite and replace agrach, cgraph, drawable_graph, il_graph with new API
* Refactor graph API and fix unit test and multiple leaks
Update Wrapper for graph identifier
Ordered Nodes in graph drawable
Fix icfg and several agraph refactor issues
Use kahn to get topo sort in assign_layers
Introduce khan for assign_layer and find DAG cycle and backedges in algorithm
* Fix self loop and update db test
* Solve request changes
* Fix cbpf db
* Fix test graph warning in testing NULL deletion
* Fix mismatched rz_agraph_compute_layout nonnull
* Fix memleak
* Clean and fix code
* Fix memleak in graph free
* Fix memleak in matrix implement
* Add bindgen doc
* Fix memleak in early exit
* Fix rz-bindgen warning comments
* Make graph structures private.
* Fix Windows C2036
* Fix typo in type annotation.
* Add new type annotations for RzGraph and HtPP
---------
Co-authored-by: Heersin <teablearcher@gmail.com>
