Skip to content

Instantly share code, notes, and snippets.

@FauxFaux

FauxFaux/bsearch.ghidra.c

Last active July 13, 2023 21:00
Show Gist options
  • Save FauxFaux/6a85e39fc29c01dfce872a8f67e7f6cb to your computer and use it in GitHub Desktop.
Save FauxFaux/6a85e39fc29c01dfce872a8f67e7f6cb to your computer and use it in GitHub Desktop.
Download ZIP
Raw
bsearch.ghidra.c
/* WARNING: Globals starting with '_' overlap smaller symbols at the same address */
/* butt::work */
undefined [16] butt::work(long **param_1,long param_2,uint *param_3)
{
long **pplVar1;
uint *puVar2;
long *plVar3;
long lVar4;
ulong uVar5;
ulong uVar6;
ulong uVar7;
ulong uVar8;
ulong uVar9;
ulong uVar10;
char cVar11;
undefined sum [16];
uint local_48;
uint uStack_44;
uint uStack_40;
uint uStack_3c;
if (param_2 == 0) {
uVar5 = 0;
}
else {
pplVar1 = param_1 + param_2;
uVar5 = 0;
param_3 = &local_48;
do {
plVar3 = *param_1;
param_1 = param_1 + 1;
uVar7 = plVar3[2];
if (uVar7 != 0) {
local_48 = SUB164(_.LCPI0_0,0);
uStack_44 = SUB164(_.LCPI0_0,4);
uStack_40 = SUB164(_.LCPI0_0,8);
uStack_3c = SUB164(_.LCPI0_0,0xc);
lVar4 = *plVar3;
uVar9 = 0;
uVar10 = uVar7;
uVar6 = uVar7;
do {
while( true ) {
uVar8 = (uVar10 >> 1) + uVar9;
puVar2 = (uint *)(lVar4 + uVar8 * 8);
cVar11 = *puVar2 != local_48;
if (*puVar2 < local_48) {
cVar11 = -1;
}
if (cVar11 == '\x01') break;
if (cVar11 != -1) {
uVar5 = (ulong)(uint)((int)uVar5 + *(int *)(lVar4 + 4 + uVar8 * 8));
goto LAB_001000d5;
}
uVar9 = uVar8 + 1;
uVar10 = uVar6 - uVar9;
if (uVar6 < uVar9 || uVar10 == 0) goto LAB_001000d5;
}
uVar10 = uVar8 - uVar9;
uVar6 = uVar8;
} while (uVar9 <= uVar8 && uVar10 != 0);
LAB_001000d5:
uVar9 = 0;
uVar10 = uVar7;
uVar6 = uVar7;
do {
while( true ) {
uVar8 = (uVar10 >> 1) + uVar9;
puVar2 = (uint *)(lVar4 + uVar8 * 8);
cVar11 = *puVar2 != uStack_44;
if (*puVar2 < uStack_44) {
cVar11 = -1;
}
if (cVar11 == '\x01') break;
if (cVar11 != -1) {
uVar5 = (ulong)(uint)((int)uVar5 + *(int *)(lVar4 + 4 + uVar8 * 8));
goto LAB_00100125;
}
uVar9 = uVar8 + 1;
uVar10 = uVar6 - uVar9;
if (uVar6 < uVar9 || uVar10 == 0) goto LAB_00100125;
}
uVar10 = uVar8 - uVar9;
uVar6 = uVar8;
} while (uVar9 <= uVar8 && uVar10 != 0);
LAB_00100125:
uVar9 = 0;
uVar10 = uVar7;
uVar6 = uVar7;
do {
while( true ) {
uVar8 = (uVar10 >> 1) + uVar9;
puVar2 = (uint *)(lVar4 + uVar8 * 8);
cVar11 = *puVar2 != uStack_40;
if (*puVar2 < uStack_40) {
cVar11 = -1;
}
if (cVar11 == '\x01') break;
if (cVar11 != -1) {
uVar5 = (ulong)(uint)((int)uVar5 + *(int *)(lVar4 + 4 + uVar8 * 8));
goto LAB_00100175;
}
uVar9 = uVar8 + 1;
uVar10 = uVar6 - uVar9;
if (uVar6 < uVar9 || uVar10 == 0) goto LAB_00100175;
}
uVar10 = uVar8 - uVar9;
uVar6 = uVar8;
} while (uVar9 <= uVar8 && uVar10 != 0);
LAB_00100175:
uVar6 = 0;
uVar10 = uVar7;
do {
while( true ) {
uVar9 = (uVar7 >> 1) + uVar6;
puVar2 = (uint *)(lVar4 + uVar9 * 8);
cVar11 = *puVar2 != uStack_3c;
if (*puVar2 < uStack_3c) {
cVar11 = -1;
}
if (cVar11 == '\x01') break;
if (cVar11 != -1) {
uVar5 = (ulong)(uint)((int)uVar5 + *(int *)(lVar4 + 4 + uVar9 * 8));
goto LAB_00100045;
}
uVar6 = uVar9 + 1;
uVar7 = uVar10 - uVar6;
if (uVar10 < uVar6 || uVar7 == 0) goto LAB_00100045;
}
uVar7 = uVar9 - uVar6;
uVar10 = uVar9;
} while (uVar6 <= uVar9 && uVar7 != 0);
}
LAB_00100045:
} while (param_1 != pplVar1);
}
sum._8_8_ = param_3;
sum._0_8_ = uVar5;
return sum;
}
Raw
bsearch.rs
// in the crate root:
// #![feature(test)]
extern crate test;
use std::hint::black_box;
use test::Bencher;
const N: u16 = 30_000;
fn items() -> Vec<(u16, u16)> {
(0..N).zip(0..N).collect::<Vec<_>>()
}
#[bench]
fn foo(b: &mut Bencher) {
let items = (0..100).map(|_| black_box(items())).collect::<Vec<_>>();
b.iter(|| {
let mut sum = 0;
for list in &items {
for i in black_box([4, 58, 817, 7481]) {
if let Ok(v) = list.binary_search_by_key(&i, |&(a, _)| a) {
sum += v;
}
}
}
sum
});
}
Raw
bsearch2.ghidra.c
/* WARNING: Globals starting with '_' overlap smaller symbols at the same address */
/* butt::work */
undefined [16] butt::work(long **haystacks,long haystack_count,uint *param_3)
{
long *plVar1;
ulong sum;
ulong list_length_maybe;
ulong tested_offset;
ulong tested_offset_follower;
ulong advanced_by;
ulong previous_test;
char not_found;
undefined ret [16];
uint target_1;
uint target_2;
uint target_3;
uint target_4;
long current_list;
uint *current_value;
long **last_haystack;
if (haystack_count == 0) {
sum = 0;
}
else {
last_haystack = haystacks + haystack_count;
sum = 0;
param_3 = &target_1;
do {
plVar1 = *haystacks;
haystacks = haystacks + 1;
list_length_maybe = plVar1[2];
if (list_length_maybe != 0) {
target_1 = SUB164(_INPUT_DATA,0);
target_2 = SUB164(_INPUT_DATA,4);
target_3 = SUB164(_INPUT_DATA,8);
target_4 = SUB164(_INPUT_DATA,0xc);
current_list = *plVar1;
tested_offset_follower = 0;
advanced_by = list_length_maybe;
previous_test = list_length_maybe;
do {
while( true ) {
tested_offset = (advanced_by >> 1) + tested_offset_follower;
current_value = (uint *)(current_list + tested_offset * 8);
not_found = *current_value != target_1;
if (*current_value < target_1) {
not_found = -1;
}
if (not_found == '\x01') break;
if (not_found != -1) {
sum = (ulong)(uint)((int)sum + *(int *)(current_list + 4 + tested_offset * 8));
goto test_item_2;
}
tested_offset_follower = tested_offset + 1;
advanced_by = previous_test - tested_offset_follower;
if (previous_test < tested_offset_follower || advanced_by == 0) goto test_item_2;
}
advanced_by = tested_offset - tested_offset_follower;
previous_test = tested_offset;
} while (tested_offset_follower <= tested_offset && advanced_by != 0);
test_item_2:
tested_offset_follower = 0;
advanced_by = list_length_maybe;
previous_test = list_length_maybe;
do {
while( true ) {
tested_offset = (advanced_by >> 1) + tested_offset_follower;
current_value = (uint *)(current_list + tested_offset * 8);
not_found = *current_value != target_2;
if (*current_value < target_2) {
not_found = -1;
}
if (not_found == '\x01') break;
if (not_found != -1) {
sum = (ulong)(uint)((int)sum + *(int *)(current_list + 4 + tested_offset * 8));
goto LAB_00100125;
}
tested_offset_follower = tested_offset + 1;
advanced_by = previous_test - tested_offset_follower;
if (previous_test < tested_offset_follower || advanced_by == 0) goto LAB_00100125;
}
advanced_by = tested_offset - tested_offset_follower;
previous_test = tested_offset;
} while (tested_offset_follower <= tested_offset && advanced_by != 0);
LAB_00100125:
tested_offset_follower = 0;
advanced_by = list_length_maybe;
previous_test = list_length_maybe;
do {
while( true ) {
tested_offset = (advanced_by >> 1) + tested_offset_follower;
current_value = (uint *)(current_list + tested_offset * 8);
not_found = *current_value != target_3;
if (*current_value < target_3) {
not_found = -1;
}
if (not_found == '\x01') break;
if (not_found != -1) {
sum = (ulong)(uint)((int)sum + *(int *)(current_list + 4 + tested_offset * 8));
goto LAB_00100175;
}
tested_offset_follower = tested_offset + 1;
advanced_by = previous_test - tested_offset_follower;
if (previous_test < tested_offset_follower || advanced_by == 0) goto LAB_00100175;
}
advanced_by = tested_offset - tested_offset_follower;
previous_test = tested_offset;
} while (tested_offset_follower <= tested_offset && advanced_by != 0);
LAB_00100175:
previous_test = 0;
advanced_by = list_length_maybe;
do {
while( true ) {
tested_offset_follower = (list_length_maybe >> 1) + previous_test;
current_value = (uint *)(current_list + tested_offset_follower * 8);
not_found = *current_value != target_4;
if (*current_value < target_4) {
not_found = -1;
}
if (not_found == '\x01') break;
if (not_found != -1) {
sum = (ulong)(uint)((int)sum + *(int *)(current_list + 4 + tested_offset_follower * 8)
);
goto LAB_00100045;
}
previous_test = tested_offset_follower + 1;
list_length_maybe = advanced_by - previous_test;
if (advanced_by < previous_test || list_length_maybe == 0) goto LAB_00100045;
}
list_length_maybe = tested_offset_follower - previous_test;
advanced_by = tested_offset_follower;
} while (previous_test <= tested_offset_follower && list_length_maybe != 0);
}
LAB_00100045:
} while (haystacks != last_haystack);
}
ret._8_8_ = param_3;
ret._0_8_ = sum;
return ret;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment