CODEWITHSUNDEEP
calgorithmsortingquicksortstrcmp
user3435580
user3435580

Reputation: 576

C What kind of sorting algorithm is this?

I decompiled a application and found what seems like some kind of sorting algorithm 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 bsearch C standard looks like decompiled

int __cdecl bsearch(int a1, int a2, unsigned int a3, int a4, int (__cdecl *a5)(_DWORD, _DWORD))
{
  unsigned int v5; // ebx@1
  int v6; // eax@2

  v5 = a3;
  if ( !a3 )
    return 0;
  while ( 1 )
  {
    v6 = a5(a1, a2 + (v5 >> 1) * a4);
    if ( v6 < 0 )
    {
      v5 >>= 1;
      goto LABEL_6;
    }
    if ( !v6 )
      return a2 + (v5 >> 1) * a4;
    a2 += (v5 >> 1) * a4 + a4;
    v5 = v5 - (v5 >> 1) - 1;
LABEL_6:
    if ( !v5 )
      return 0;
  }
}

Answer could be found at : https://reverseengineering.stackexchange.com/questions/4139/c-what-kind-of-sorting-algorithm-is-this/

Upvotes: 1

Views: 140

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 133995

Looks like a binary search to me. Note that there isn't any swapping of items, so it's unlikely to be a sort. Looks like it's finding the first occurrence of the string a1, or where a1 would be inserted, in a sorted array of strings.

Note the expression:

v6 = v8 + a4 * (v9 - v8) / a4 / 2;

This is finding the midpoint between v8 and v9. Then you have a call to the string comparison, and different behavior based on whether the comparison result is less, equal, or greater.

Upvotes: 3

Related Questions