Take the 2-minute tour ×
Reverse Engineering Stack Exchange is a question and answer site for researchers and developers who explore the principles of a system through analysis of its structure, function, and operation. It's 100% free, no registration required.

I decompiled a application and found what seems like some kind of sorting algorithm, I was told it's not even a sorting algorithm, but a binary search on stackoverflow

I just don't know which one it is can someone let me know it's actual name?

whatever is passed into the strcmpi wrapper is in some area's divided by 2 who knows some crazy stuff.. I thought it was qsort (quicksort) since it's a standard library for C. But i'm not sure.

int __cdecl SomeKindOfSortAlgorithm(int a1, int a2, int a3, signed int a4, int (__cdecl *a5)(unsigned int, unsigned int), int a6)
{
  int v6; // esi@1
  int result; // eax@1
  int v8; // ebp@2
  int v9; // edi@2

  v6 = 0;
  result = 0;
  *(unsigned int *)a6 = 0;
  if ( !a3 )
    return result;
  v8 = a2;
  v9 = a2 + a4 * (a3 - 1);
  if ( a2 > (unsigned int)v9 )
  {
LABEL_9:
    if ( result > 0 )
      v6 += a4;
    return v6;
  }
  while ( 1 )
  {
    v6 = v8 + a4 * (v9 - v8) / a4 / 2;
    result = a5(a1, v8 + a4 * (v9 - v8) / a4 / 2);
    if ( result < 0 )
    {
      if ( v6 == a2 )
        goto LABEL_9;
      v9 = v6 - a4;
      goto LABEL_8;
    }
    if ( result <= 0 )
      break;
    v8 = v6 + a4;
LABEL_8:
    if ( v8 > (unsigned int)v9 )
      goto LABEL_9;
  }
  *(unsigned int *)a6 = 1;
  if ( v6 == a2 )
  {
LABEL_15:
    result = a2;
  }
  else
  {
    while ( 1 )
    {
      v6 -= a4;
      if ( a5(a1, v6) )
        break;
      if ( v6 == a2 )
        goto LABEL_15;
    }
    result = v6 + a4;
  }
  return result;
}

Here is the compare function

int __cdecl StrCmpiWrapper(const char *Str1, const char **a2)
{
  return _strcmpi(Str1, *a2);
}

Here is how you use it.

  int ChatMsgBuffer;
  int v4; // eax@1
  int v5; // eax@5
  int v8; // [sp+10h] [bp-4h]@1

  v4 = SomeKindOfSortAlgorithm(
         ChatMsgBuffer,
         textFile->Pointer,
         textFile->TotalElements,
         4,
         (int (__cdecl *)(unsigned int, unsigned int))StrCmpiWrapper,
         (int)&v8);

  if ( !v8 && v4 )
  {
      //Allocate memory .. copy it and other stuff here.
  }

Here is how a real qsort looks when decompiled

void __cdecl sub_4015D0(int a1, unsigned int a2, unsigned int a3, unsigned int a4, int (__cdecl *a5)(_DWORD, _DWORD, _DWORD), int a6)
{
  unsigned int v6; // esi@2
  int v7; // edi@9
  unsigned int v8; // esi@32
  int v9; // esi@38
  unsigned int k; // edi@41
  unsigned int v11; // edi@43
  void *v12; // edi@52
  int j; // [sp+Ch] [bp-20h]@52
  unsigned int v14; // [sp+10h] [bp-1Ch]@16
  int v15; // [sp+14h] [bp-18h]@11
  int v16; // [sp+14h] [bp-18h]@16
  unsigned int v17; // [sp+18h] [bp-14h]@9
  int v18; // [sp+1Ch] [bp-10h]@2
  unsigned int v19; // [sp+28h] [bp-4h]@2
  unsigned int i; // [sp+38h] [bp+Ch]@38

  while ( a3 )
  {
    if ( a2 <= 0x20 )
      goto LABEL_37;
    v19 = a1 + a4 * a2;
    v6 = a1 + a4 * (a2 >> 1);
    v18 = a4 + v6;
    sub_401420(a1, a1 + a4 * (a2 >> 1), a1 + a4 * a2 - a4, a4, a5, a6);
    while ( a1 < v6 && !a5(v6 - a4, v6, a6) )
      v6 -= a4;
    while ( v18 < v19 && !a5(v18, v6, a6) )
      v18 += a4;
    v7 = v18;
    v17 = v6;
    while ( 1 )
    {
      while ( 1 )
      {
        for ( ; v7 < v19; v7 += a4 )
        {
          v15 = a5(v6, v7, a6);
          if ( v15 >= 0 )
          {
            if ( v15 > 0 )
              break;
            sub_401160(v18, v7, a4);
            v18 += a4;
          }
        }
        if ( a1 < v17 )
        {
          do
          {
            v14 = v17 - a4;
            v16 = a5(v17 - a4, v6, a6);
            if ( v16 >= 0 )
            {
              if ( v16 > 0 )
                break;
              v6 -= a4;
              sub_401160(v6, v14, a4);
            }
            v17 -= a4;
          }
          while ( a1 < v14 );
        }
        if ( v17 == a1 )
          break;
LABEL_27:
        if ( v7 == v19 )
        {
          v17 -= a4;
          v18 -= a4;
          v6 -= a4;
          if ( v17 == v6 )
            sub_401160(v6, v18, a4);
          else
            sub_401220(v17, v18, v6, a4);
        }
        else
        {
          v17 -= a4;
          sub_401160(v7, v17, a4);
          v7 += a4;
        }
      }
      if ( v7 == v19 )
        break;
      if ( v17 != a1 )
        goto LABEL_27;
      if ( v18 == v7 )
        sub_401160(v7, v6, a4);
      else
        sub_401220(v7, v6, v18, a4);
      v7 += a4;
      v6 += a4;
      v18 += a4;
    }
    a3 = (a3 >> 2) + (a3 >> 1);
    v8 = (v6 - a1) / a4;
    a2 = (v19 - v18) / a4;
    if ( v8 > a2 )
    {
      sub_4015D0(v18, a2, a3, a4, a5, a6);
      a2 = v8;
    }
    else
    {
      sub_4015D0(a1, v8, a3, a4, a5, a6);
      a1 = v18;
    }
  }
  if ( a2 <= 0x20 )
  {
LABEL_37:
    if ( a2 > 1 )
    {
      v9 = a1;
      for ( i = a2 - 1; i; --i )
      {
        v9 += a4;
        if ( a5(v9, a1, a6) >= 0 )
        {
          v12 = (void *)v9;
          for ( j = v9; ; v12 = (void *)j )
          {
            j -= a4;
            if ( a5(v9, j, a6) >= 0 )
              break;
          }
          if ( v12 != (void *)v9 )
            sub_401310(v12, v9, a4);
        }
        else
        {
          sub_401310((void *)a1, v9, a4);
        }
      }
    }
    return;
  }
  for ( k = a2 >> 1; k; sub_401500(a1, k, a2, a4, a5, a6) )
    --k;
  v11 = a1 + a4 * a2;
  while ( a2 > 1 )
  {
    v11 -= a4;
    sub_401160(a1, v11, a4);
    --a2;
    sub_401500(a1, 0, a2, a4, a5, a6);
  }
}

int __cdecl sub_401420(int a1, int a2, int a3, unsigned int a4, int a5, int a6)
{
  unsigned int v6; // edi@2
  int result; // eax@2

  if ( 40 * a4 >= a3 - a1 )
  {
    result = sub_4013B0(a1, a2, a3, a4, a5, a6);
  }
  else
  {
    v6 = a4 * (((a3 - a1) / a4 >> 3) + 1);
    sub_4013B0(a1, v6 + a1, a1 + 2 * v6, a4, a5, a6);
    sub_4013B0(a2 - v6, a2, a2 + v6, a4, a5, a6);
    sub_4013B0(a3 - 2 * v6, a3 - v6, a3, a4, a5, a6);
    result = sub_4013B0(a1 + v6, a2, a3 - v6, a4, a5, a6);
  }
  return result;
}

int __cdecl sub_401500(int a1, unsigned int a2, unsigned int a3, int a4, int (__cdecl *a5)(_DWORD, _DWORD, _DWORD), int a6)
{
  int v6; // ebx@1
  int v7; // esi@1
  int i; // edi@1
  int result; // eax@6
  unsigned int v10; // ebx@7
  unsigned int v11; // edi@7
  int v12; // [sp+Ch] [bp-4h]@1

  v12 = a2;
  v6 = 2 * a2 + 2;
  v7 = a1 + a4 * a2;
  for ( i = a1 + a4 * (2 * a2 + 2); v6 <= a3; i = a1 + a4 * v6 )
  {
    if ( v6 == a3 || a5(i, i - a4, a6) < 0 )
    {
      --v6;
      i -= a4;
    }
    sub_401160(v7, i, a4);
    a2 = v6;
    v7 = i;
    v6 = 2 * v6 + 2;
  }
  result = v12;
  if ( v12 < a2 )
  {
    do
    {
      v10 = (a2 - 1) >> 1;
      v11 = a1 + a4 * ((a2 - 1) >> 1);
      result = a5(v7, a1 + a4 * ((a2 - 1) >> 1), a6);
      if ( result <= 0 )
        break;
      sub_401160(v11, v7, a4);
      a2 = (a2 - 1) >> 1;
      v7 = v11;
      result = v12;
    }
    while ( v12 < v10 );
  }
  return result;
}
share|improve this question

1 Answer 1

up vote 8 down vote accepted

It's a binary search. I've renamed several of the variables, and in one case, introduced a new variable, because one of the local variables was used for one thing in the first half of the function and something else in the second half of the function.

The only tricky part is that once it finds an occurrence of the string to find, it iterates to find the first occurrence.

#include <string.h>

typedef const char* MYTYPE;
typedef char* PTR_TYPE;

PTR_TYPE __cdecl SomeKindOfSortAlgorithm(MYTYPE elementToFind, PTR_TYPE array, unsigned int numElts, unsigned int eltSize, int (__cdecl *compare)(MYTYPE, PTR_TYPE), bool* pFound)
{
  PTR_TYPE mid; // esi@1
  int result; // eax@1
  PTR_TYPE lower_bound; // ebp@2
  PTR_TYPE upper_bound; // edi@2

  mid = 0;
  result = 0;
  *pFound = false;
  if ( !numElts )
    return NULL;
  lower_bound = array;
  upper_bound = array + eltSize * (numElts - 1);
  if ( array > upper_bound )
  {
NOT_FOUND:
    if ( result > 0 )
      mid += eltSize;
    return mid;
  }
  while ( 1 )
  {
    mid = lower_bound + eltSize * (upper_bound - lower_bound) / eltSize / 2;
    result = compare(elementToFind, mid);
    if ( result < 0 ) // elementToFind should go before mid
    {
      if ( mid == array )
        goto NOT_FOUND;
      upper_bound = mid - eltSize;
      goto CHECK_LOOP_END;
    }
    if ( result <= 0 ) // elementToFind equals the element at mid
      break;
    // elementToFind should go after mid
    lower_bound = mid + eltSize;
CHECK_LOOP_END:
    if ( lower_bound > upper_bound )
      goto NOT_FOUND;
  }

  PTR_TYPE pFirstOccurrance;
  *pFound = true;
  if ( mid == array )
  {
AT_FIRST_ELEMENT:
    pFirstOccurrance = array;
  }
  else
  {
    while ( 1 )
    {
      mid -= eltSize;
      if ( compare(elementToFind, mid) ) // elementToFind != element at mid
        break;
      if ( mid == array )
        goto AT_FIRST_ELEMENT;
    }
    pFirstOccurrance = mid + eltSize;
  }
  return pFirstOccurrance;
}

int __cdecl StrCmpiWrapper(MYTYPE element, PTR_TYPE arrayPointer)
{
  return _strcmpi(element, *(MYTYPE*)arrayPointer);
}


int main(int argc, char* argv[])
{
  MYTYPE lookFor = "def";
  MYTYPE* pFirstOccurrance; // eax@1
  bool found; // [sp+10h] [bp-4h]@1

  MYTYPE data[3] = {
      "abc",
      "def",
      "ghi"
  };

  pFirstOccurrance = (MYTYPE*)SomeKindOfSortAlgorithm(
         lookFor,
         (PTR_TYPE)data,
         3,
         sizeof(MYTYPE),
         StrCmpiWrapper,
         &found);

  if ( !found && pFirstOccurrance )
  {
      //Allocate memory .. copy it and other stuff here.
  }

    return 0;
}
share|improve this answer
    
Thanks for putting your time into it, I couldn't find any new variables you added just found you moved the double of mid equation into one. nevermind found it PTR_TYPE pFirstOccurrance; –  user3435580 Apr 25 at 7:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.