Rizin
unix-like reverse engineering framework and cli tools
Functions | Variables
debruijn.c File Reference
#include <rz_util.h>

Go to the source code of this file.

Functions

static void de_bruijn_seq (int prenecklace_len_t, int lyndon_prefix_len_p, int order, int maxlen, int size, int *prenecklace_a, char *sequence, const char *charset)
 
static char * de_bruijn (const char *charset, int order, int maxlen)
 
RZ_API RZ_OWN char * rz_debruijn_pattern (int size, int start, const char *charset)
 Generate a cyclic pattern following the Debruijn pattern. More...
 
RZ_API int rz_debruijn_offset (int start, const char *charset, ut64 value, bool is_big_endian)
 Finds the offset of a given value in a debrujn sequence. More...
 

Variables

static const char * debruijn_charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"
 

Function Documentation

◆ de_bruijn()

static char* de_bruijn ( const char *  charset,
int  order,
int  maxlen 
)
static

Definition at line 47 of file debruijn.c.

47  {
48  if (!charset) {
49  return NULL;
50  }
51  size_t size = strlen(charset);
52  int *prenecklace_a = calloc(size * (size_t)order, sizeof(int));
53  if (!prenecklace_a) {
54  return NULL;
55  }
56  char *sequence = calloc(maxlen + 1, sizeof(char));
57  if (!sequence) {
58  free(prenecklace_a);
59  return NULL;
60  }
61  de_bruijn_seq(1, 1, order, maxlen, size, prenecklace_a, sequence, charset);
62  free(prenecklace_a);
63  return sequence;
64 }
NULL
#define NULL
Definition: cris-opc.c:27
de_bruijn_seq
static void de_bruijn_seq(int prenecklace_len_t, int lyndon_prefix_len_p, int order, int maxlen, int size, int *prenecklace_a, char *sequence, const char *charset)
Definition: debruijn.c:15
free
RZ_API void Ht_() free(HtName_(Ht) *ht)
Definition: ht_inc.c:130
size
voidpf void uLong size
Definition: ioapi.h:138
calloc
void * calloc(size_t number, size_t size)
Definition: malloc.c:102
maxlen
ut64 maxlen
Definition: core.c:76

References calloc(), de_bruijn_seq(), free(), maxlen, and NULL.

Referenced by rz_debruijn_pattern().

◆ de_bruijn_seq()

static void de_bruijn_seq ( int  prenecklace_len_t,
int  lyndon_prefix_len_p,
int  order,
int  maxlen,
int  size,
int *  prenecklace_a,
char *  sequence,
const char *  charset 
)
static

Definition at line 15 of file debruijn.c.

16  {
17  int j;
18  if (!charset || !sequence || strlen(sequence) == maxlen) {
19  return;
20  }
21  if (prenecklace_len_t > order) {
22  if (order % lyndon_prefix_len_p == 0) {
23  for (j = 1; j <= lyndon_prefix_len_p; j++) {
24  sequence[strlen(sequence)] = charset[prenecklace_a[j]];
25  if (strlen(sequence) == maxlen) {
26  return;
27  }
28  }
29  }
30  } else {
31  prenecklace_a[prenecklace_len_t] =
32  prenecklace_a[prenecklace_len_t - lyndon_prefix_len_p];
33  de_bruijn_seq(prenecklace_len_t + 1, lyndon_prefix_len_p, order, maxlen,
34  size, prenecklace_a, sequence, charset);
35  for (j = prenecklace_a[prenecklace_len_t - lyndon_prefix_len_p] + 1;
36  j < size; j++) {
37  prenecklace_a[prenecklace_len_t] = j;
38  de_bruijn_seq(prenecklace_len_t + 1, prenecklace_len_t, order, maxlen,
39  size, prenecklace_a, sequence, charset);
40  }
41  }
42 }

References maxlen.

Referenced by de_bruijn().

◆ rz_debruijn_offset()

RZ_API int rz_debruijn_offset ( int  start,
const char *  charset,
ut64  value,
bool  is_big_endian 
)

Finds the offset of a given value in a debrujn sequence.

Parameters
startStarting offset in the Debruijn pattern
charsetSet of characters to use to generate the sequence
valueValue to search in the sequence
is_big_endianEndianess of value
Returns
The offset in the sequence where value is found or -1 if not found

Definition at line 112 of file debruijn.c.

112  {
113  int retval = -1;
114  // 0x10000 should be long enough. This is how peda works, and nobody complains
115  // ... but is slow. Optimize for common case.
116  int lens[] = { 0x1000, 0x10000, 0x100000 };
117  int j;
118 
119  if (value == 0) {
120  return -1;
121  }
122 
123  for (j = 0; j < RZ_ARRAY_SIZE(lens) && retval == -1; j++) {
124  char *pattern = rz_debruijn_pattern(lens[j], start, charset);
125  if (!pattern) {
126  return -1;
127  }
128 
129  char buf[9];
130  buf[8] = '\0';
131  if (is_big_endian) {
132  rz_write_be64(buf, value);
133  } else {
134  rz_write_le64(buf, value);
135  }
136  char *needle;
137  for (needle = buf; !*needle; needle++) {
138  /* do nothing here */
139  }
140 
141  char *pch = strstr(pattern, needle);
142  if (pch) {
143  retval = (int)(size_t)(pch - pattern);
144  }
145  free(pattern);
146  }
147  return retval;
148 }
value
static int value
Definition: cmd_api.c:93
start
static static sync static getppid static getegid const char static filename char static len const char char static bufsiz static mask static vfork const void static prot static getpgrp const char static swapflags static arg static fd static protocol static who struct sockaddr static addrlen static backlog struct timeval struct timezone static tz const struct iovec static count static mode const void const struct sockaddr static tolen const char static pathname void static offset struct stat static buf void long static basep static whence static length const void static len static semflg const void static shmflg const struct timespec struct timespec static rem const char static group const void start
Definition: sflib.h:133
rz_debruijn_pattern
RZ_API RZ_OWN char * rz_debruijn_pattern(int size, int start, const char *charset)
Generate a cyclic pattern following the Debruijn pattern.
Definition: debruijn.c:80
buf
voidpf void * buf
Definition: ioapi.h:138
is_big_endian
bool MACH0_() is_big_endian(struct MACH0_(obj_t) *bin)
Definition: mach0.c:3312
rz_write_be64
static void rz_write_be64(void *dest, ut64 val)
Definition: rz_endian.h:119
rz_write_le64
static void rz_write_le64(void *dest, ut64 val)
Definition: rz_endian.h:277
RZ_ARRAY_SIZE
#define RZ_ARRAY_SIZE(x)
Definition: rz_types.h:300
int
static int
Definition: sfsocketcall.h:114

References free(), int, is_big_endian(), RZ_ARRAY_SIZE, rz_debruijn_pattern(), rz_write_be64(), rz_write_le64(), start, and value.

Referenced by rz_main_rz_gg(), and rz_write_debruijn_find_handler().

◆ rz_debruijn_pattern()

RZ_API RZ_OWN char* rz_debruijn_pattern ( int  size,
int  start,
const char *  charset 
)

Generate a cyclic pattern following the Debruijn pattern.

Generate a cyclic pattern of desired size, and charset, return with starting offset of start.

For example, AAABAACAAD is a sequence of size 10, start 0, charset = debruijn_charset.

Parameters
sizeSize of the string to return
startStarting offset in the Debruijn pattern
charsetSet of characters to use to generate the string
Returns
String of length size allocated on the heap

Definition at line 80 of file debruijn.c.

80  {
81  rz_return_val_if_fail(size >= 0, NULL);
82  rz_return_val_if_fail(start >= 0, NULL);
83  if (!charset) {
84  charset = debruijn_charset;
85  }
86  char *pat = de_bruijn(charset, 3, size + start);
87  if (!pat || start == 0) {
88  return pat;
89  }
90 
91  char *pat2 = RZ_NEWS0(char, size + 1);
92  if (!pat2) {
93  free(pat);
94  return NULL;
95  }
96  size_t len = strlen(pat + start);
97  rz_return_val_if_fail(len <= size, NULL);
98  strcpy(pat2, pat + start);
99  free(pat);
100  return pat2;
101 }
len
size_t len
Definition: 6502dis.c:15
de_bruijn
static char * de_bruijn(const char *charset, int order, int maxlen)
Definition: debruijn.c:47
debruijn_charset
static const char * debruijn_charset
Definition: debruijn.c:12
rz_return_val_if_fail
#define rz_return_val_if_fail(expr, val)
Definition: rz_assert.h:108
RZ_NEWS0
#define RZ_NEWS0(x, y)
Definition: rz_types.h:282

References de_bruijn(), debruijn_charset, free(), len, NULL, RZ_NEWS0, rz_return_val_if_fail, and start.

Referenced by __printPattern(), initialize_stack(), rz_debruijn_offset(), rz_egg_pattern(), and rz_write_debruijn_handler().

Variable Documentation

◆ debruijn_charset

const char* debruijn_charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz1234567890"
static

Definition at line 12 of file debruijn.c.

Referenced by rz_debruijn_pattern().