/src/yara/libyara/bitmask.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | Copyright (c) 2018. The YARA Authors. All Rights Reserved. |
3 | | |
4 | | Redistribution and use in source and binary forms, with or without modification, |
5 | | are permitted provided that the following conditions are met: |
6 | | |
7 | | 1. Redistributions of source code must retain the above copyright notice, this |
8 | | list of conditions and the following disclaimer. |
9 | | |
10 | | 2. Redistributions in binary form must reproduce the above copyright notice, |
11 | | this list of conditions and the following disclaimer in the documentation and/or |
12 | | other materials provided with the distribution. |
13 | | |
14 | | 3. Neither the name of the copyright holder nor the names of its contributors |
15 | | may be used to endorse or promote products derived from this software without |
16 | | specific prior written permission. |
17 | | |
18 | | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
19 | | ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
20 | | WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
21 | | DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR |
22 | | ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
23 | | (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
24 | | LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON |
25 | | ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
26 | | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
27 | | SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
28 | | */ |
29 | | |
30 | | #include <assert.h> |
31 | | #include <yara/bitmask.h> |
32 | | #include <yara/utils.h> |
33 | | |
34 | | //////////////////////////////////////////////////////////////////////////////// |
35 | | // Find the smallest offset within bitmask A where bitmask B can be accommodated |
36 | | // without bit collisions. A collision occurs when both bitmasks have a bit set |
37 | | // to 1 at the same offset. This function assumes that the first bit in B is 1 |
38 | | // and do optimizations that rely on that. |
39 | | // |
40 | | // The function also receives a pointer to an uint32_t where the function stores |
41 | | // a value that is used for speeding-up subsequent searches over the same |
42 | | // bitmask A. When called for the first time with some bitmask A, the pointer |
43 | | // must point to a zero-initialized uint32_t. In the next call the function uses |
44 | | // the previously stored value for skipping over a portion of the A bitmask and |
45 | | // updates the value. |
46 | | // |
47 | | // Args: |
48 | | // a: Bitmask A |
49 | | // b: Bitmask B |
50 | | // len_a: Length of bitmask A in bits |
51 | | // len_b: Length of bitmask B in bits |
52 | | // off_a: Address of an uint32_t indicating the offset within bitmask A where |
53 | | // to start searching. In the first call to it must point to a 0 value. |
54 | | // This function updates the value to use it in subsequent calls. |
55 | | // Returns: |
56 | | // The smaller offset within bitmask A where bitmask B can be put. |
57 | | // |
58 | | uint32_t yr_bitmask_find_non_colliding_offset( |
59 | | YR_BITMASK* a, |
60 | | YR_BITMASK* b, |
61 | | uint32_t len_a, |
62 | | uint32_t len_b, |
63 | | uint32_t* off_a) |
64 | 0 | { |
65 | 0 | uint32_t i, j, k; |
66 | | |
67 | | // Ensure that the first bit of bitmask B is set, as this function does some |
68 | | // optimizations that rely on that. |
69 | 0 | assert(yr_bitmask_is_set(b, 0)); |
70 | | |
71 | | // Skip all slots that are filled with 1s. It's safe to do that because the |
72 | | // first bit of B is 1, so we won't be able to accommodate B at any offset |
73 | | // within such slots. |
74 | 0 | for (i = *off_a / YR_BITMASK_SLOT_BITS; |
75 | 0 | i <= len_a / YR_BITMASK_SLOT_BITS && a[i] == -1L; |
76 | 0 | i++) |
77 | 0 | ; |
78 | |
|
79 | 0 | *off_a = i; |
80 | |
|
81 | 0 | for (; i <= len_a / YR_BITMASK_SLOT_BITS; i++) |
82 | 0 | { |
83 | | // The slot is filled with 1s, we can safely skip it. |
84 | 0 | if (a[i] == -1L) |
85 | 0 | continue; |
86 | | |
87 | 0 | for (j = 0; j <= yr_min(len_a, YR_BITMASK_SLOT_BITS - 1); j++) |
88 | 0 | { |
89 | 0 | bool found = true; |
90 | |
|
91 | 0 | for (k = 0; k <= len_b / YR_BITMASK_SLOT_BITS; k++) |
92 | 0 | { |
93 | 0 | YR_BITMASK m = b[k] << j; |
94 | |
|
95 | 0 | if (j > 0 && k > 0) |
96 | 0 | m |= b[k - 1] >> (YR_BITMASK_SLOT_BITS - j); |
97 | |
|
98 | 0 | if ((i + k <= len_a / YR_BITMASK_SLOT_BITS) && (m & a[i + k]) != 0) |
99 | 0 | { |
100 | 0 | found = false; |
101 | 0 | break; |
102 | 0 | } |
103 | 0 | } |
104 | |
|
105 | 0 | if (found) |
106 | 0 | return i * YR_BITMASK_SLOT_BITS + j; |
107 | 0 | } |
108 | 0 | } |
109 | | |
110 | 0 | return len_a; |
111 | 0 | } |