検索犬のテスト問題、復号と符号化について

21560 ワード

余談:久しぶりに更新しましたが、この間は同時に2つのプロジェクトを担いでいて、本当に彼の世話をする暇がありません.一つ終わったら、また仕事を探し始めます.自分の作ったプロジェクトをまとめたいと思っていたので、しばらく待っていましょう.
 
今日は検索学校の募集をして、メールでテストをするように知らせてくれました.隣のMMはテストのホームページを开いてヒントを発见して彼女がすでにテストに合格したことをおめでとうございますと言って、私は开いて1つのテーマがそこに置いてあるようで、30分で终わると言います.
タイトルは符号化の関数を与えて、復号部分のコードを与えることを要求して、それからプログラムを実行して、実行結果を提出します.コードは次のとおりです.
#include  <stdio.h> 

#include  <stdlib.h> 

#include  "stdint.h" 

#include  <assert.h> 

#include  <string.h> 





int  encode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len) 

{ 

  const  uint8_t*  in  =  (const  uint8_t*)raw_in; 

  uint8_t*  out  =  (uint8_t*)raw_out; 



  uint32_t  seed  =  password  ^  0x48879c19u; 

  for  (size_t  i  =  0  ;  i  <  len;  ++i)  { 

    uint8_t  a  =  (  in[i]  ^  seed  )  >>  4; 

    uint8_t  b  =  (  (  ((uint32_t)in[i])  <<  11  )  ^  seed  )  >>  (11-4); 

    a  &=  15; 

    b  &=  240; 

    a  =  15  &  (  a  ^  (b  <<  3)); 

    out[i]  =  a  |  b; 

    seed  =  ((seed  ^  in[i])  *  144123481  +  in[i]); 

  }

  return 0;

} 





int  decode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len) 

{ 

  const  uint8_t*  in  =  (const  uint8_t*)raw_in; 

  uint8_t*  out  =  (uint8_t*)raw_out; 



  uint32_t  seed  =  password  ^  0x48879c19u; 

  for  (size_t  i  =  0  ;  i  <  len;  ++i)  { 

    //   ? ? ? ? ? ? ? ?

  } 

  return 0;

} 

int  main() 

{ 

  const  uint8_t  buf1[]  =  {0xc7,  0x23,  0xed,  0x9b,  0x26,  0x0b,  0x51,  0xe4,  0x79,  0x5d,  0x57,  0x0d,  0xbb,  0xca,  0x5d,  0x28,  0xa4,  0xf9,  0x60,  0xcc,  0x65,  0x35,  0x82,  0xa9,  0x2e,  0xe6,  0x03,  0x7c,  0x7d,  0x49,  0x1f,  0x58,  0x0e,  0xbe,  0xd5,  0x49,  0x68,  0x44,  }; 

  uint8_t  buf2[100]  =  {}; 

  const  uint32_t  password  =  0xf765d3bau; 

  const  size_t  len  =  sizeof(buf1); 

  decode(buf1,  buf2,  password,  len); 

  printf("%s
"
, buf2); }

私はこのコードを見たばかりで目がくらくらして、このようなコードスタイルが好きではありません.無理にコードの関数を読んで、紙の上でよく推理してみると、もともとはin[i]とseedを異様に操作し、その後aはin[i]の高さ4桁、bはin[i]の低4桁、そしてaとbの位置を交換していた.
a = 15 & ( a ^ (b << 3)); この文は完全に気にする必要はありませんが、元のバイトを得るには、aとbを先に異或前の位置に復元し(この一連を操作逆置と理解することができます)、seedと異或し、原理はx^y^y=xです.これにより、既存のビットを取得し、シフトすることで復号後の答えを得ることができます.
int  decode(const  void*  raw_in,  void*  raw_out,  uint32_t  password,  size_t  len) 

{ 

  const  uint8_t*  in  =  (const  uint8_t*)raw_in; 

  uint8_t*  out  =  (uint8_t*)raw_out; 



  uint32_t  seed  =  password  ^  0x48879c19u; 

  for  (size_t  i  =  0  ;  i  <  len;  ++i)  { 

    //   ? ? ? ? ? ? ? ?

    uint8_t a = (in[i] << 4) ^ seed;

    uint8_t b = (((uint32_t)in[i]) << 7 ^ seed) >> 11;

    a &= 240;

    b &= 15;

    out[i] = a | b;

    seed  =  ((seed  ^  out[i])  *  144123481  +  out[i]); 

  } 

  return 0;

} 

これは私が2回目のテストをした問題で、前のテストはずっと合格していません.その問題とこの問題の違いはaが上位5位、bが下位3位で、seedの計算が少し違います.しかし、結果は間違っていて、私は結果に不思議な思いをしている間に、弾枠は私がもう時間になったと言った.そこで再ログインし、2回目のテストを行います.今回は従来のdecodeコードを使い続け、この版のencodeに数値を置き換えて合格しました.コードを取り消して最初のテストに戻り、何回かチェックしたが、結果は依然として間違っていた.夜にコードをひっくり返してみると、2回目に通過できたのは偶然だった.aとbはそれぞれ4位を取ったからだ.
私が間違った原因は、aとbを復元するとき、aの後3位置0、bの前5位置0を間違って使用し続けるべきで、私は前の数値を誤って使用し続け、aの前3位置0、bの後5位置0を招いたからです.自分で検査したのはまだ細かくないようだ.
ここでもう一つのケースはVSのライブラリにstdintがないことです.h、そこで私はネット上で1つ探して、下に貼るしかありません:
 
// ISO C9x  compliant stdint.h for Microsoft Visual Studio

// Based on ISO/IEC 9899:TC2 Committee draft (May 6, 2005) WG14/N1124 

// 

//  Copyright (c) 2006-2008 Alexander Chemeris

// 

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are met:

// 

//   1. Redistributions of source code must retain the above copyright notice,

//      this list of conditions and the following disclaimer.

// 

//   2. Redistributions in binary form must reproduce the above copyright

//      notice, this list of conditions and the following disclaimer in the

//      documentation and/or other materials provided with the distribution.

// 

//   3. The name of the author may be used to endorse or promote products

//      derived from this software without specific prior written permission.

// 

// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED

// WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF

// MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO

// EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;

// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 

// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR

// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// 

///////////////////////////////////////////////////////////////////////////////



#ifndef _MSC_VER // [

#error "Use this header only with Microsoft Visual C++ compilers!"

#endif // _MSC_VER ]



#ifndef _MSC_STDINT_H_ // [

#define _MSC_STDINT_H_



#if _MSC_VER > 1000

#pragma once

#endif



#include <limits.h>



// For Visual Studio 6 in C++ mode and for many Visual Studio versions when

// compiling for ARM we should wrap <wchar.h> include with 'extern "C++" {}'

// or compiler give many errors like this:

//   error C2733: second C linkage of overloaded function 'wmemchr' not allowed

#ifdef __cplusplus

extern "C" {

#endif

#  include <wchar.h>

#ifdef __cplusplus

}

#endif



// Define _W64 macros to mark types changing their size, like intptr_t.

#ifndef _W64

#  if !defined(__midl) && (defined(_X86_) || defined(_M_IX86)) && _MSC_VER >= 1300

#     define _W64 __w64

#  else

#     define _W64

#  endif

#endif





// 7.18.1 Integer types



// 7.18.1.1 Exact-width integer types



// Visual Studio 6 and Embedded Visual C++ 4 doesn't

// realize that, e.g. char has the same size as __int8

// so we give up on __intX for them.

#if (_MSC_VER < 1300)

typedef signed char       int8_t;

typedef signed short      int16_t;

typedef signed int        int32_t;

typedef unsigned char     uint8_t;

typedef unsigned short    uint16_t;

typedef unsigned int      uint32_t;

#else

typedef signed __int8     int8_t;

typedef signed __int16    int16_t;

typedef signed __int32    int32_t;

typedef unsigned __int8   uint8_t;

typedef unsigned __int16  uint16_t;

typedef unsigned __int32  uint32_t;

#endif

typedef signed __int64       int64_t;

typedef unsigned __int64     uint64_t;





// 7.18.1.2 Minimum-width integer types

typedef int8_t    int_least8_t;

typedef int16_t   int_least16_t;

typedef int32_t   int_least32_t;

typedef int64_t   int_least64_t;

typedef uint8_t   uint_least8_t;

typedef uint16_t  uint_least16_t;

typedef uint32_t  uint_least32_t;

typedef uint64_t  uint_least64_t;



// 7.18.1.3 Fastest minimum-width integer types

typedef int8_t    int_fast8_t;

typedef int16_t   int_fast16_t;

typedef int32_t   int_fast32_t;

typedef int64_t   int_fast64_t;

typedef uint8_t   uint_fast8_t;

typedef uint16_t  uint_fast16_t;

typedef uint32_t  uint_fast32_t;

typedef uint64_t  uint_fast64_t;



// 7.18.1.4 Integer types capable of holding object pointers

#ifdef _WIN64 // [

typedef signed __int64    intptr_t;

typedef unsigned __int64  uintptr_t;

#else // _WIN64 ][

typedef _W64 signed int   intptr_t;

typedef _W64 unsigned int uintptr_t;

#endif // _WIN64 ]



// 7.18.1.5 Greatest-width integer types

typedef int64_t   intmax_t;

typedef uint64_t  uintmax_t;





// 7.18.2 Limits of specified-width integer types



#if !defined(__cplusplus) || defined(__STDC_LIMIT_MACROS) // [   See footnote 220 at page 257 and footnote 221 at page 259



// 7.18.2.1 Limits of exact-width integer types

#define INT8_MIN     ((int8_t)_I8_MIN)

#define INT8_MAX     _I8_MAX

#define INT16_MIN    ((int16_t)_I16_MIN)

#define INT16_MAX    _I16_MAX

#define INT32_MIN    ((int32_t)_I32_MIN)

#define INT32_MAX    _I32_MAX

#define INT64_MIN    ((int64_t)_I64_MIN)

#define INT64_MAX    _I64_MAX

#define UINT8_MAX    _UI8_MAX

#define UINT16_MAX   _UI16_MAX

#define UINT32_MAX   _UI32_MAX

#define UINT64_MAX   _UI64_MAX



// 7.18.2.2 Limits of minimum-width integer types

#define INT_LEAST8_MIN    INT8_MIN

#define INT_LEAST8_MAX    INT8_MAX

#define INT_LEAST16_MIN   INT16_MIN

#define INT_LEAST16_MAX   INT16_MAX

#define INT_LEAST32_MIN   INT32_MIN

#define INT_LEAST32_MAX   INT32_MAX

#define INT_LEAST64_MIN   INT64_MIN

#define INT_LEAST64_MAX   INT64_MAX

#define UINT_LEAST8_MAX   UINT8_MAX

#define UINT_LEAST16_MAX  UINT16_MAX

#define UINT_LEAST32_MAX  UINT32_MAX

#define UINT_LEAST64_MAX  UINT64_MAX



// 7.18.2.3 Limits of fastest minimum-width integer types

#define INT_FAST8_MIN    INT8_MIN

#define INT_FAST8_MAX    INT8_MAX

#define INT_FAST16_MIN   INT16_MIN

#define INT_FAST16_MAX   INT16_MAX

#define INT_FAST32_MIN   INT32_MIN

#define INT_FAST32_MAX   INT32_MAX

#define INT_FAST64_MIN   INT64_MIN

#define INT_FAST64_MAX   INT64_MAX

#define UINT_FAST8_MAX   UINT8_MAX

#define UINT_FAST16_MAX  UINT16_MAX

#define UINT_FAST32_MAX  UINT32_MAX

#define UINT_FAST64_MAX  UINT64_MAX



// 7.18.2.4 Limits of integer types capable of holding object pointers

#ifdef _WIN64 // [

#  define INTPTR_MIN   INT64_MIN

#  define INTPTR_MAX   INT64_MAX

#  define UINTPTR_MAX  UINT64_MAX

#else // _WIN64 ][

#  define INTPTR_MIN   INT32_MIN

#  define INTPTR_MAX   INT32_MAX

#  define UINTPTR_MAX  UINT32_MAX

#endif // _WIN64 ]



// 7.18.2.5 Limits of greatest-width integer types

#define INTMAX_MIN   INT64_MIN

#define INTMAX_MAX   INT64_MAX

#define UINTMAX_MAX  UINT64_MAX



// 7.18.3 Limits of other integer types



#ifdef _WIN64 // [

#  define PTRDIFF_MIN  _I64_MIN

#  define PTRDIFF_MAX  _I64_MAX

#else  // _WIN64 ][

#  define PTRDIFF_MIN  _I32_MIN

#  define PTRDIFF_MAX  _I32_MAX

#endif  // _WIN64 ]



#define SIG_ATOMIC_MIN  INT_MIN

#define SIG_ATOMIC_MAX  INT_MAX



#ifndef SIZE_MAX // [

#  ifdef _WIN64 // [

#     define SIZE_MAX  _UI64_MAX

#  else // _WIN64 ][

#     define SIZE_MAX  _UI32_MAX

#  endif // _WIN64 ]

#endif // SIZE_MAX ]



// WCHAR_MIN and WCHAR_MAX are also defined in <wchar.h>

#ifndef WCHAR_MIN // [

#  define WCHAR_MIN  0

#endif  // WCHAR_MIN ]

#ifndef WCHAR_MAX // [

#  define WCHAR_MAX  _UI16_MAX

#endif  // WCHAR_MAX ]



#define WINT_MIN  0

#define WINT_MAX  _UI16_MAX



#endif // __STDC_LIMIT_MACROS ]





// 7.18.4 Limits of other integer types



#if !defined(__cplusplus) || defined(__STDC_CONSTANT_MACROS) // [   See footnote 224 at page 260



// 7.18.4.1 Macros for minimum-width integer constants



#define INT8_C(val)  val##i8

#define INT16_C(val) val##i16

#define INT32_C(val) val##i32

#define INT64_C(val) val##i64



#define UINT8_C(val)  val##ui8

#define UINT16_C(val) val##ui16

#define UINT32_C(val) val##ui32

#define UINT64_C(val) val##ui64



// 7.18.4.2 Macros for greatest-width integer constants

#define INTMAX_C   INT64_C

#define UINTMAX_C  UINT64_C



#endif // __STDC_CONSTANT_MACROS ]





#endif // _MSC_STDINT_H_ ]