C 这是什么排序算法？

逆向工程 艾达 反编译 C
2021-06-21 16:19:55

我反编译了一个应用程序，发现似乎是某种排序算法，有人告诉我它甚至不是排序算法，而是 stackoverflow 上的二分搜索

我只是不知道它是哪一个，有人可以让我知道它的实际名称吗？

传递到 strcmpi 包装器的任何内容都在某个区域除以 2 谁知道一些疯狂的东西..我认为它是 qsort（快速排序），因为它是 C 的标准库。但我不确定。

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;
}

这是比较功能

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

这是你如何使用它。

  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.
  }

这是反编译时真正的 qsort 的样子

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;
}
1个回答

这是一个二分搜索。我重命名了几个变量，在一种情况下，引入了一个新变量，因为其中一个局部变量在函数的前半部分用于一件事，而在函数的后半部分用于另一件事。

唯一棘手的部分是，一旦它找到要查找的字符串的出现，它就会迭代以找到第一次出现。

#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;
}
其它你可能感兴趣的问题
上一篇正确的 IDA PRO 控制流图 下一篇从二进制或 ipa 进行逆向工程