WWW.LAB-Z.COM – 第 97 页

Step to UEFI (10) —- 让程序 Pause 一下的方法

很多时候我们编写的一些工具需要支持暂停的功能，比如：ls 列出的文件名时最好能够响应用户的按键，暂停一下以便用户查看结果。查看了一下Shell方面的代码，可以通过 Shell Environment 2 提供的函数来实现。

当然，我不愿意使用庞大的 Shell Library，选择性的提取一些代码就OK

//
// PauseTest.c
//
#include <Uefi.h>
#include <Library/UefiLib.h>
#include <Library/ShellLib.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/UefiApplicationEntryPoint.h>
#include <Library/BaseMemoryLib.h>

#define SHELL_INTERFACE_PROTOCOL \
  { \
    0x47c7b223, 0xc42a, 0x11d2, 0x8e, 0x57, 0x0, 0xa0, 0xc9, 0x69, 0x72, 0x3b \
  }
EFI_GUID        ShellInterfaceProtocol  = SHELL_INTERFACE_PROTOCOL;
EFI_GUID		SEGuid = EFI_SE_EXT_SIGNATURE_GUID;
//
// The shell environment is provided by a driver.  The shell links to the
// shell environment for services.  In addition, other drivers may connect
// to the shell environment and add new internal command handlers, or
// internal protocol handlers.
//
#define SHELL_ENVIRONMENT_INTERFACE_PROTOCOL \
  { \
    0x47c7b221, 0xc42a, 0x11d2, 0x8e, 0x57, 0x0, 0xa0, 0xc9, 0x69, 0x72, 0x3b \
  }
EFI_GUID        ShellEnvProtocol = SHELL_ENVIRONMENT_INTERFACE_PROTOCOL;

#define EFI_OUTPUT_PAUSE    0x00000002

typedef struct {
  SHELLENV_EXECUTE          Execute;  // Execute a command line
  SHELLENV_GET_ENV          GetEnv;   // Get an environment variable
  SHELLENV_GET_MAP          GetMap;   // Get mapping tables
  SHELLENV_ADD_CMD          AddCmd;   // Add an internal command handler
  SHELLENV_ADD_PROT         AddProt;  // Add protocol info handler
  SHELLENV_GET_PROT         GetProt;  // Get the protocol ID
  SHELLENV_CUR_DIR          CurDir;
  SHELLENV_FILE_META_ARG    FileMetaArg;
  SHELLENV_FREE_FILE_LIST   FreeFileList;

  //
  // The following services are only used by the shell itself
  //
  SHELLENV_NEW_SHELL        NewShell;
  SHELLENV_BATCH_IS_ACTIVE  BatchIsActive;

  SHELLENV_FREE_RESOURCES   FreeResources;
} EFI_SHELL_ENVIRONMENT;

EFI_SHELL_INTERFACE             *SI;
EFI_SHELL_ENVIRONMENT           *SE;
EFI_SHELL_ENVIRONMENT2          *SE2;

EFI_BOOT_SERVICES     *gBS;
EFI_RUNTIME_SERVICES  *gRT;
EFI_SYSTEM_TABLE      *gST;

//Copy from \Shell\Library\Misc.c
BOOLEAN
GrowBuffer (
  IN OUT EFI_STATUS   *Status,
  IN OUT VOID         **Buffer,
  IN UINTN            BufferSize
  )
/*++

Routine Description:

  Helper function called as part of the code needed
  to allocate the proper sized buffer for various 
  EFI interfaces.

Arguments:

  Status      - Current status

  Buffer      - Current allocated buffer, or NULL

  BufferSize  - Current buffer size needed
    
Returns:
    
  TRUE - if the buffer was reallocated and the caller 
  should try the API again.

--*/
{
  BOOLEAN TryAgain;

  //
  // If this is an initial request, buffer will be null with a new buffer size
  //
  if (NULL == *Buffer && BufferSize) {
    *Status = EFI_BUFFER_TOO_SMALL;
  }
  //
  // If the status code is "buffer too small", resize the buffer
  //
  TryAgain = FALSE;
  if (*Status == EFI_BUFFER_TOO_SMALL) {

    if (*Buffer) {
      FreePool (*Buffer);
    }

    *Buffer = AllocateZeroPool (BufferSize);

    if (*Buffer) {
      TryAgain = TRUE;
    } else {
      *Status = EFI_OUT_OF_RESOURCES;
    }
  }
  //
  // If there's an error, free the buffer
  //
  if (!TryAgain && EFI_ERROR (*Status) && *Buffer) {
    FreePool (*Buffer);
    *Buffer = NULL;
  }

  return TryAgain;
}

//Copy from \Shell\Library\Handle.c
EFI_STATUS
LocateHandle (
  IN EFI_LOCATE_SEARCH_TYPE       SearchType,
  IN EFI_GUID                     * Protocol OPTIONAL,
  IN VOID                         *SearchKey OPTIONAL,
  IN OUT UINTN                    *NoHandles,
  OUT EFI_HANDLE                  **Buffer
  )
/*++

Routine Description:

  Function returns an array of handles that support the requested protocol 
  in a buffer allocated from pool.

Arguments:

  SearchType           - Specifies which handle(s) are to be returned.
  Protocol             - Provides the protocol to search by.   
                         This parameter is only valid for SearchType ByProtocol.
  SearchKey            - Supplies the search key depending on the SearchType.
  NoHandles            - The number of handles returned in Buffer.
  Buffer               - A pointer to the buffer to return the requested array of 
                         handles that support Protocol.

Returns:
  
  EFI_SUCCESS           - The result array of handles was returned.
  EFI_NOT_FOUND         - No handles match the search. 
  EFI_OUT_OF_RESOURCES - There is not enough pool memory to store the matching results.

--*/
{
  EFI_STATUS  Status;
  UINTN       BufferSize;

  //
  // Initialize for GrowBuffer loop
  //
  Status      = EFI_SUCCESS;
  *Buffer     = NULL;
  BufferSize  = 50 * sizeof (EFI_HANDLE);

  //
  // Call the real function
  //
  while (GrowBuffer (&Status, (VOID **) Buffer, BufferSize)) {
    Status = gBS->LocateHandle (
                  SearchType,
                  Protocol,
                  SearchKey,
                  &BufferSize,
                  *Buffer
                  );
  }

  *NoHandles = BufferSize / sizeof (EFI_HANDLE);
  if (EFI_ERROR (Status)) {
    *NoHandles = 0;
  }

  return Status;
}

INTN
CompareGuidx (
  IN EFI_GUID     *Guid1,
  IN EFI_GUID     *Guid2
  )
/*++

Routine Description:

  Compares to GUIDs

Arguments:

  Guid1 - guid to compare
  Guid2 - guid to compare

Returns:
  =  0  if Guid1 == Guid2
  != 0  if Guid1 != Guid2 

--*/
{
  INT32 *g1;
  INT32 *g2;
  INT32 r;

  //
  // Compare 32 bits at a time
  //
  g1  = (INT32 *) Guid1;
  g2  = (INT32 *) Guid2;

  r   = g1[0] - g2[0];
  r |= g1[1] - g2[1];
  r |= g1[2] - g2[2];
  r |= g1[3] - g2[3];

  return r;
}
// Copy from \Shell\Library\Init.c
EFI_STATUS
LibInitializeShellApplication (
  IN EFI_HANDLE                   ImageHandle,
  IN EFI_SYSTEM_TABLE             *SystemTable
  )
{
  EFI_STATUS  Status;
  EFI_HANDLE  *HandleBuffer;
  UINTN       HandleNum;
  UINTN       HandleIndex;
  EFI_GUID         SESGuid         = EFI_SE_EXT_SIGNATURE_GUID;
  
  //
  // Connect to the shell interface
  //
  Status = gBS->HandleProtocol (ImageHandle, &ShellInterfaceProtocol, (VOID *) &SI);
  if (EFI_ERROR (Status)) {
    Print (L"InitShellApp: Application not started from Shell\n");
    gBS->Exit (ImageHandle, Status, 0, NULL);
  }

  //
  // Connect to the shell environment
  //
  Status = gBS->HandleProtocol (
                ImageHandle,
                &ShellEnvProtocol,
                (VOID *) &SE2
                );
  if (EFI_ERROR (Status) || !(CompareGuid (&SE2->SESGuid, &SESGuid) == 0 &&
    (SE2->MajorVersion > EFI_SHELL_MAJOR_VER ||
      (SE2->MajorVersion == EFI_SHELL_MAJOR_VER && SE2->MinorVersion >= 
EFI_SHELL_MINOR_VER))
    )
  ) {
    Status = LocateHandle (
              ByProtocol,
              &ShellEnvProtocol,
              NULL,
              &HandleNum,
              &HandleBuffer
              );
    if (EFI_ERROR (Status)) {
      Print (L"InitShellApp: 1Shell environment interfaces not found\n");
      gBS->Exit (ImageHandle, Status, 0, NULL);
    }

    Status = EFI_NOT_FOUND;
    for (HandleIndex = 0; HandleIndex < HandleNum; HandleIndex++) {
      gBS->HandleProtocol (
           HandleBuffer[HandleIndex],
           &ShellEnvProtocol,
           (VOID *) &SE2
           );
      if (CompareGuidx (&SE2->SESGuid, &SESGuid) == 0)
	  {
        Status = EFI_SUCCESS;
        break;
      }
    }

    FreePool (HandleBuffer);

    if (EFI_ERROR (Status)) {
      Print (L"InitShellApp: 2Shell environment interfaces not found\n");
      gBS->Exit (ImageHandle, Status, Status, NULL);
    }
  }

  SE = (EFI_SHELL_ENVIRONMENT *) SE2;
  
  //
  // Done with init
  //
  return Status;
}

//
// Entry point function 
//
EFI_STATUS
UefiMain (
  IN EFI_HANDLE        ImageHandle,
  IN EFI_SYSTEM_TABLE  *SystemTable
  )
{
   INTN	i;

  Print(L"You can't Pause by Tab key\n");
  for (i=0;i<1000;i++)
    {
	Print(L".");
    }
  Print(L".\n");
  gBS = SystemTable -> BootServices;

  LibInitializeShellApplication (ImageHandle,SystemTable);
  SE2->SetKeyFilter(SE2->GetKeyFilter() | EFI_OUTPUT_PAUSE);
  
  Print(L"You can Pause by Tab key");
  for (i=0;i<1000;i++)
    {
  	Print(L".");
    }

  return EFI_SUCCESS;
}

上面的代码演示了使用 Pause Break键来暂停输出的功能。

代码在这里下载：

PauseTest

关于前面提到的 VOL 命令的问题

前面介绍过一些Shell下常用的命令，提到了查看当前 volume 大小的命令 VOL. 在使用中，会遇到一个奇怪的问题，感觉上有时候它能输出当前盘的大小，而有时候输出的是Partition的大小，具体的原因是什么呢？下载 VOL 的代码，进行查看注意到下面的位置：

Status = RootFs->GetInfo (RootFs, &gEfiFileSystemInfoGuid, &Size, VolumeInfo);

就是说VOL命令是基于File System的，显示出来的是文件系统能够识别出来的大小。

做一个简单的实验,将U盘进行分区，下面是只有一个分区的情况

实验的结果如下：

Volume NEW VOLUME (rw)
1,003,487,232 bytes total disk space
959,131,648 bytes available on disk
4,096 bytes in each allocation unit

再使用工具将这个U盘分区

实验的结果如下：

Volume has no label (rw)
411,009,024 bytes total disk space
411,000,832 bytes available on disk
8,192 bytes in each allocation unit

显示出来的只是有文件系统的那个分区的大小。

因此,之前实验遇到的问题是:当查看的盘上只有一个分区，并且这个分区占满了全部空间的时候，显示的也是盘的大小；如果上面的分区没有占满盘的话，显示出来的只有分区大小了。

vol.c 可以在这里下载 vol

利用算法解决2048游戏

在 http://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048/22389702#22389702 上有很多大牛提出了自己的解决方法。

ovolve 使用了 a-b剪枝，这是典型的用在博弈上的算法，比如：之前的中国象棋就是用了这个方法。

Nicola Pezzotti 的特点在于贡献了一个很简易的计算局面整洁度的算法…..

问题是上面的都是 js 语言编写的，对于我来说很难理解，并且很难进行评估。

个人感觉算法本身不难，困难的是如何理解他们使用的数据结构，更具体来说困难度在于如何进行局面评估的算法（这个问题中，需要对盘面顺序程度和整体分数进行评估）。

最终，目光落在 nneonneo 的算法上。他使用了 bit-map 的技术，能够充分利用空间：每一个格子从 0-15 ，对应着 2^0 – 2^15 ，整个局面用64位即可表示。这样做大大

降低了传递参数之类的耗时，客观上节省了时间。此外，还使用数组直接存放了行列的分数，评估行列分数直接让数组值相加即可，这是非常经典的空间换时间的做法。

他的程序可以在他的 git上下载到 https://github.com/nneonneo/2048-ai ，我这里也存了一份可以在 vs2008下编译通过的

nneonneo

我的程序完全仿照了他的程序，只是没有实现他用来剪枝的泛型 typedef std::map trans_table_t; 因为我使用的 Delphi 2010 没有对应的功能，

在我的 I5 2450 上，一步大约需要2s左右。

program NeoNeo;

{$APPTYPE CONSOLE}

uses
  SysUtils,math,windows;

const
  ROW_MASK=$FFFF;
  COL_MASK=$000F000F000F000F;
  CPROB_THRESH_BASE = 0.0001;
  CACHE_DEPTH_LIMIT=1;
  SEARCH_DEPTH_LIMIT=3;
  b:array[0..13] of integer=(0,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192);
type
  board_t=int64;
  row_t=word;
  get_move_func_t = function(board:board_t):integer;
  T_eval_state=record
         cprob_thresh:single;
         maxdepth:integer;
         curdepth:integer;
         cachehits:integer;
         moves_evaled:integer;
       end;

  function score_tilechoose_node(var state:T_eval_state; board:board_t; cprob:single):single; forward;
  function reverse_row(row:row_t):row_t;  forward;
  function pack_col(col:board_t):row_t; forward;
  function unpack_col(row:row_t):board_t; forward;
  function score_move_node(Var state:t_eval_state;board:board_t; cprob:single):single; forward;

var
  row_left_table:array[0..65535] of board_t;
  row_right_table:array[0..65535] of board_t;
  col_up_table:array[0..65535] of board_t;
  col_down_table:array[0..65535] of board_t;
  line_heur_score_table:array[0..65535] of single;
  row_score_table:array[0..65535] of single;

procedure init_move_tables;
var
  row:LongWord;
  line:array[0..3] of LongWord;
  result:row_t;
  i,j:integer;
begin
  fillchar(row_left_table,0,sizeof(row_left_table));
  fillchar(row_right_table,0,sizeof(row_right_table));
  fillchar(col_up_table,0,sizeof(col_up_table));
  fillchar(col_down_table,0,sizeof(col_down_table));

  for  row:= 0 to 65535 do
    begin
      line[0]:=row and $f;
      line[1]:=(row shr 4) and $f;
      line[2]:=(row shr 8) and $f;
      line[3]:=(row shr 12) and $f;

      i:=0;
      while (i<3) do
        begin
          j:=i+1;
          //for j := i+1 to 3 do
          while (j<4) do
            begin
              if line[j]<>0 then
                  break;
              inc(j);
            end;
          if (j=4) then break;
          if (line[i]=0) then
             begin
               line[i]:=line[j];
               line[j]:=0;
               dec(i);
             end
          else
            if (line[i]=line[j]) and (line[i]<>$f) then
               begin
                 inc(line[i]);
                 line[j]:=0;
               end;
          inc(i);
        end;

      result:=(line[0]) or (line[1] shl 4) or (line[2] shl 8) or (line[3] shl 12);

      row_left_table[row]:=row xor result;
      row_right_table[reverse_row(row)]:=reverse_row(row) xor reverse_row(result);
      col_up_table[row] := unpack_col(row) xor unpack_col(result);
      col_down_table[reverse_row(row)]:=unpack_col(reverse_row(row)) xor unpack_col(reverse_row(result));
    end;
end;

function execute_move_0(var board:board_t):board_t;
var
  tmp:board_t;
  ret:board_t;
begin
  ret:=board;

  tmp:=col_up_table[pack_col((board shr (4*0))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*0));

  tmp:=col_up_table[pack_col((board shr (4*1))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*1));

  tmp:=col_up_table[pack_col((board shr (4*2))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*2));

  tmp:=col_up_table[pack_col((board shr (4*3))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*3));

  Result:=ret;
end;

function execute_move_1(var board:board_t):board_t;
var
  tmp:board_t;
  ret:board_t;
begin
  ret:=board;

  tmp:=col_down_table[pack_col((board shr (4*0))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*0));

  tmp:=col_down_table[pack_col((board shr (4*1))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*1));

  tmp:=col_down_table[pack_col((board shr (4*2))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*2));

  tmp:=col_down_table[pack_col((board shr (4*3))and $000F000F000F000F)];
  ret:=ret xor (tmp shl (4*3));

  Result:=ret;
end;

function execute_move_2(var board:board_t):board_t;
var
  tmp:board_t;
  ret:board_t;
begin
  ret:=board;

  tmp:=row_left_table[board shr (16*0) and $FFFF];
  ret:=ret xor (tmp shl (16*0));

  tmp:=row_left_table[board shr (16*1) and $FFFF];
  ret:=ret xor (tmp shl (16*1));

  tmp:=row_left_table[board shr (16*2) and $FFFF];
  ret:=ret xor (tmp shl (16*2));

  tmp:=row_left_table[board shr (16*3) and $FFFF];
  ret:=ret xor (tmp shl (16*3));

  Result:=ret;
end;

function execute_move_3(var board:board_t):board_t;
var
  tmp:board_t;
  ret:board_t;
begin
  ret:=board;

  tmp:=row_right_table[board shr (16*0) and $FFFF];
  ret:=ret xor (tmp shl (16*0));

  tmp:=row_right_table[board shr (16*1) and $FFFF];
  ret:=ret xor (tmp shl (16*1));

  tmp:=row_right_table[board shr (16*2) and $FFFF];
  ret:=ret xor (tmp shl (16*2));

  tmp:=row_right_table[board shr (16*3) and $FFFF];
  ret:=ret xor (tmp shl (16*3));

  Result:=ret;
end;

function pack_col(col:board_t):row_t;
begin
  Result:=col or (col shr 12) or (col shr 24) or (col shr 36);
end;

function unpack_col(row:row_t):board_t;
var
  tmp:board_t;
begin
  tmp:=row;
  Result:=(tmp or (tmp shl 12) or (tmp shl 24) or (tmp shl 36)) and COL_MASK;
end;

procedure print_board(board:board_t);
var
  i:integer;
begin
  for i := 0 to 3 do
    begin
      writeln(format('%4d %4d %4d %4d',
               [b[board and $f],
                b[board shr 4 and $f],
                b[board shr 8 and $f],
                b[board shr 12 and $f]]));
      board:=board shr 16;
    end;
end;

function reverse_row(row:row_t):row_t;
begin
  Result:=((row shr 12) or ((row shr 4) and $F0) or ((row shl 4) and $0F00) or (row shl 12));
end;

function execute_move(move:integer;board:board_t):Board_t;
begin
  case move of
     0://up
       begin
         Result:=execute_move_0(board);
       end;
     1://down
       begin
         Result:=execute_move_1(Board);
       end;
     2://left
       begin
         Result:=execute_move_2(board);
       end;
     3://right
       begin
         Result:=execute_move_3(Board);
       end;
     else
       Result:=0;
  end;
end;

function get_max_rank(board:board_t):integer;
var
  maxrank,k:integer;
begin
  maxrank:=0;
  while board<>0 do
    begin
      k:=board and $f;
      if k>maxrank then maxrank:=k;
      board:=board shr 4;
    end;
  Result:=maxrank;
end;

procedure init_score_tables;
var
  row:Longword;
  i,maxi:integer;
  heur_score:single;
  score:single;
  line:array[0..3] of LongWord;
  rank,maxrank:LongWord;
begin
  fillchar(line_heur_score_table,0,sizeof(line_heur_score_table));
  fillchar(row_score_table,0,sizeof(row_score_table));

  for row:= 0 to 65535 do
    begin

  line[0]:=row and $f;
  line[1]:=(row shr 4) and $f;
  line[2]:=(row shr 8) and $f;
  line[3]:=(row shr 12) and $f;

      heur_score:=0;
      score:=0;

      for i := 0 to 3 do
        begin
          rank:=line[i];

          if (rank=0) then
            begin
              heur_score:=heur_score+10000;
            end
          else
            if (rank>=2) then
              begin
                score:=score+(rank-1)*power(2,rank);
              end;
        end;

      maxi:=0;
      maxrank:=0;
      for i := 0 to 3 do
        begin
          rank:=line[i];
          if (rank>maxrank) then
             begin
               maxrank:=rank;
               maxi:=i;
             end;
        end;

      if (maxi=0) or (maxi=3) then
        heur_score:=heur_score+20000;

      for i := 1 to 3 do
        if (line[i]=line[i-1]+1) or (line[i]=line[i-1]-1) then
             heur_score:=heur_score+1000;

      if (line[0]<line[1]) and (line[1]<line[2]) and (line[2]<line[3]) then
         heur_score:=heur_score+10000;
      if (line[0]>line[1]) and (line[1]>line[2]) and (line[2]>line[3]) then
         heur_score:=heur_score+10000;

      row_score_table[row]:=score;
      line_heur_score_table[row]:=heur_score;
    end;
end;

{
function score_board(board:board_t;tbl):single;
begin
  Result:=(tbl[board and row_mask])+
          (tbl[board shr 16 and row_mask])+
          (tbl[board shr 32 and row_mask])+
          (tbl[board shr 48 and row_mask]);
end;

function score_col_board(board:board_t;tbl):single;
begin
  Result:=(tbl[pack_col[board and col_mask]])+
          (tbl[pack_col[board shr 4 and col_mask])+
          (tbl[pack_col[board shr 8 and col_mask])+
          (tbl[pack_col[board shr 12 and col_mask]);
end;
}
function score_heur_board(board:board_t):single;
begin
  Result:=(line_heur_score_table[board and row_mask])+
          (line_heur_score_table[board shr 16 and row_mask])+
          (line_heur_score_table[board shr 32 and row_mask])+
          (line_heur_score_table[board shr 48 and row_mask])+
          (line_heur_score_table[pack_col(board and col_mask)])+
          (line_heur_score_table[pack_col(board shr 4 and col_mask)])+
          (line_heur_score_table[pack_col(board shr 8 and col_mask)])+
          (line_heur_score_table[pack_col(board shr 12 and col_mask)])+100000;
end;

function score_board(board:board_t):single;
begin
  result:=(row_score_table[board and row_mask])+
          (row_score_table[(board shr 16) and row_mask] )+
          (row_score_table[(board shr 32) and row_mask])+
          (row_score_table[(board shr 48) and row_mask]);
end;

function score_tilechoose_node(var state:T_eval_state; board:board_t; cprob:single):single;
var
  res:single;
  num_open,i:integer;
begin
  res:=0;
  num_open:=0;

  for i:=0 to 15 do
    begin
      //tmp:=board shr (4*i);
    if (board shr (4*i) and $f)=0 then
      inc(num_open);
    end;

  cprob:=cprob /num_open;

  for i := 0 to 15 do
    begin
      if ((board shr (4*i)) and $f =0) then
        begin
          res:=res+score_move_node(state,board or (Board_t (1) shl (4*i)),cprob *0.9) *0.9;
          res:=res+score_move_node(state,board or (Board_t (2) shl (4*i)),cprob *0.1) *0.1;
        end;
    end;

  Result:=Res / num_open;
end;

function score_move_node(Var state:t_eval_state;board:board_t; cprob:single):single;
var
  move:integer;
  best:single;
  res:single;
  newboard:board_t;
  //i:IsingleMapIterator;
begin
  if (cprob<state.cprob_thresh) or (state.curdepth >= SEARCH_DEPTH_LIMIT) then
    begin
      if (state.curdepth > state.curdepth) then
        begin
          state.maxdepth:=state.curdepth;
        end;
      Result:=score_heur_board(board);
      exit;
    end;

{   if (state.curdepth < CACHE_DEPTH_LIMIT) then
     begin
//       i:=state.trans_table.Find(board);
       if state.trans_table.Count(board)>0 then
         begin
           inc(state.cachehits,1);
           Result:=state.trans_table.Find(board).Value;
           exit;
         end;

     end;    }
   best:=0;

   inc(state.curdepth);
   for move := 0 to 3 do
     begin
       newboard:=execute_move(move,board);
       inc(state.moves_evaled);
       if (board = newboard) then
         continue;
       res:=score_tilechoose_node(state,newboard,cprob);
       if res > best then
         best:=res;
     end;
   dec(state.curdepth);

   {if state.curdepth < CACHE_DEPTH_LIMIT then
     begin end; //state.trans_table[board]:=best;}

   result:=best;
end;

function t_score_toplevel_move(var state:t_eval_state;board:board_t;move:integer):single;
var
  newboard:board_t;
begin
  newboard:=execute_move(move,board);
  if board=newboard then
    begin
      Result:=0;
      exit;
    end;

  state.cprob_thresh:=CPROB_THRESH_BASE;

  Result:=score_tilechoose_node(state,newboard,1)+1e-6;
end;


function score_toplevel_move(board:board_t; move:integer):single;
var
  res:single;
  start,finish:DWORD;
  state:t_eval_state;
begin

  state.cprob_thresh:=0;
  state.maxdepth:=0;
  state.curdepth:=0;
  state.cachehits:=0;
  state.moves_evaled:=0;

  start:=GetTickCount;
  res:=t_score_toplevel_move(state,board,move);
  finish:=GetTickCount;

  writeln(format('Move %d: result %f: eval %d moves ',
      [move,res,state.moves_evaled])+'in '+IntToStr(Finish-Start)+' ms');
  result:=res;
end;

function find_best_move(board:board_t):integer;
var
   move:integer;
   best:single;
   bestmove:integer;
   res:single;
begin
  best:=0;
  bestmove:=-1;

  print_board(board);
  writeln(format('Current scores: heur %.0f, actual %.0f',[score_heur_board(board),score_board(board)]));
  for move := 0 to 3 do
    begin
      res:=score_toplevel_move(board,move);
      if (res>best) then
        begin
          best:=res;
          bestmove:=move;
        end;
    end;
  Result:=bestmove;
end;

function draw_tile:integer;
begin
  if Random(9)=0 then Result:=2
  else  Result:=1;
end;

function insert_tile_rand(board:board_t;tile:integer):board_t;
var
  num_open:integer;
  i,index:integer;
  tmp:board_t;
begin
  num_open:=0;
  for i := 0 to 15 do
    if (board shr (4*i) and $f)=0 then
      begin
        inc(num_open)
      end;
  if num_open =0 then
    begin
      writeln('insert_tile_rand:no open spots!');
      Result:= board;
      exit;
    end;

  index:=random(num_open);
  for i := 0 to 15 do
    begin
      if ((board shr (4*i))and $f)<>0 then
         continue;
      if (index=0) then
         begin
           tmp:=tile;
           board:=board or (tmp shl (4 *i));
           break;
         end;
      dec(index);
    end;
  Result:=board;
end;

function initial_board:board_t;
var
   board:board_t;
   i:integer;
begin
  randomize;
  board:=0;
  for i := 0 to 1 do
    board:=insert_tile_rand(board,draw_tile);
  Result:=board;
end;

procedure play_game(get_move:get_move_func_t);
var
  board:board_t;
  moveno:integer;
  scorepenalty:integer;
  move:integer;
  newboard:board_t;
  tile:integer;
begin

  board:=initial_board;

  moveno:=0;
  scorepenalty:=0;

  while True do
    begin
      move:=0;
      while move<4 do
        begin
          if execute_move(move,board)<>board then
              break;
          inc(move);
        end;

      if move=4 then break;

      inc(moveno);
      writeln(format('Move %d , current score=%.0f, %d',[moveno,score_board(board)-scorepenalty,scorepenalty]));

      move:=get_move(board);
      if (move < 0) then break;

      newboard:=execute_move(move,board);
      if (newboard=board) then
        begin
          writeln('Illegal move!');
          dec(moveno);
          continue;
        end;

      tile:=draw_tile;
      if tile=2 then inc(scorepenalty,4);
      board:=insert_tile_rand(newboard,tile);
      writeln;
    end;
   print_board(board);
   writeln(Format('Game Over. Your score is %.0f. The hightest rank you achieved was %d.',[score_board(board)-scorepenalty,get_max_rank(board)]));
end;

//Main
begin
  init_move_tables;
  init_score_tables;
  play_game (find_best_move);
  readln;
end.

目前上面这个程序可以达到 1024 （超长发挥可以达到2048）

后面会进行的改进：

1.使用整数代替程序中的single进行局面分数的评估。

2.实现nneonneo的剪枝算法，计划使用HouSisong大牛的DGL泛型库 http://blog.csdn.net/housisong/article/category/152693

2014/4/26 修正了盘面分数的问题：

修改之前
res:=res+score_move_node(state,board or 1 shl (4*i),cprob *0.9) *0.9;

修改之后
res:=res+score_move_node(state,board or (Board_t (1) shl (4*i)),cprob *0.9) *0.9;

小游戏 2048 Delphi 命令行复刻版

最近的一款名为 2048 的小游戏很火

可以在 http://gabrielecirulli.github.io/2048/ 这里看到一个网页版，基于 HTML5，只需要用方向键让两两相同的数字碰撞就会诞生一个翻倍的数字，初始数字由 2 或者 4 构成，直到游戏界面全部被填满，游戏结束。

我使用 delphi 编写了一个 console 版的，速度更快，不过界面没有原来的版本好看：（和人类打交道不是我的长项……

2048

源程序2048re

分离GOP和VBT文件的工具

一个用于分离GOP和VBT文件的工具

这个工具是用来分离Intel Baytrail公版BIOS中的VBT和GOP文件的。其中的GOP是传统意义上的VBIOS，VBT文件是他的配置文件。在之前，配置

信息通常会写入到VBIOS中，但是在BayTrail上他们是分开独立的。

用法：

BTYGVS [文件名]

比如：BTYGVS IFWI_2013_10_01 即可在当前目录下生成这个BIOS中

包括的GOP和VBT。

下载

bytgvs

Step to UEFI (9)—-使用RDTSC计算当前CPU 频率

很早之前Intel曾经提供过一个使用RDTSC在DOS下计算CPU频率的程序（在CPUID的Datasheet中）。简单的说就是延时一个固定的时间，然后看这个时间内经过了多少个指令周期，经过计算就能得到CPU的频率。下面的程序实现了在UEFI环境下计算频率的功能，同时也可以作为插入汇编指令的参考。需要注意，这是32位UEFI环境下，如果在64位的Shell环境下这样做是不行的。

//
// FreqCalc.C
//

#include <Uefi.h>
#include <Library/UefiLib.h>
#include <Library/ShellLib.h>

EFI_SYSTEM_TABLE	*gST;
EFI_BOOT_SERVICES  	*gBS;

UINT64 rdtsc()
{
  UINT64 value;
  __asm
  {
     rdtsc
     mov dword ptr value,eax
     mov dword ptr [value + 4],edx
  } 

  return  value;
}

//
// Entry point function - ShowVersion
//
EFI_STATUS
EFIAPI
UefiMain (
  IN EFI_HANDLE        ImageHandle,
  IN EFI_SYSTEM_TABLE  *SystemTable
  )
{

  UINT64  elsp;

  gST = SystemTable;
  gBS = SystemTable->BootServices;

  elsp=rdtsc();
  gBS -> Stall(1000000);  
  Print(L"CPU Frequency: %ld \n", rdtsc()-elsp);

  return EFI_SUCCESS;
}

程序运行的结果：

虚拟机中运行的CPUZ读取的结果：

代码下载

FreqCalc

特别的，有资料指出在当前的多核环境下，这样的方法并不准确，具体的原因请参考下面的文章

1. http://blog.csdn.net/solstice/article/details/5196544 “多核时代不宜再用 x86 的 RDTSC 指令测试指令周期和时间”
2. http://blog.chinaunix.net/uid-24774106-id-2779245.html “使用rdtsc指令，测量程序的运行速度”

介绍几个 UEFI Shell下的命令（下）

继续介绍 Shell 下面的命令。

ECHO 和DOS下的这个命令相同，这是用来回显“字符串的”，比如下面的例子

MAP 这是一个“定义用户名和设备handle映射关系”的命令。最常见的用途就是给支持文件protocol的设备分配一个盘符，比如： fs0:

另外，最常见的用法是当你进入shell之后发现忘记插入U盘，插入之后U盘的盘符不会马上可以使用，这时候可以使用 map -r 一下，让他识别。

SET 和DOS下的这个命令相同，设置环境变量。SPEC中提到，不加额外参数设定的变量是“易非失”的，这次启动在，断电再上电还是在（我试验过）。

如果使用 -v 可以设置一个“易失”的变量，断电一次就没了。前面有 “×” 表示这个变量是易失的。

VOL 显示当前的硬盘/分区容量，如果你发现Windows无法正常安装不妨试试这个命令检查一下是否使用了错误的eMMC. （后面会查看一下这个命令的代码确定究竟查看的是硬盘容量还是分区容量）

VER 显示当前使用的UEFI版本信息

TIME 显示和设置当前的时间信息（不知道如何设置时区？）

TYPE 和DOS下的这个命令相同，显示文件的内容，支持普通的ASCII和UNICODE编码。

介绍几个 UEFI Shell下的命令（上）

这里只介绍常用的，因为不常用的我也搞不明白。第一个需要了解的是：很多命令可以在后面加入 -b 来做分屏显示。这个参数在查看help的时候非常有用。

比如下面就是运行 help -b 的结果

下面是简单介绍一些命令。

alias 可以用来给一些命令设置“别名”。比如：我们在Shell下可以用 dir 和ls一样列出当前目录就是因为设置 dir 为 ls的别名。

实验一下，我们设置 alias dog ls,那么输入 dog 也和ls一样

attribute 更改文件属性，和DOS下面的那个命令一样

直接运行可以列出文件的属性

支持通配符，比如下面给这几个文件加上只读属性之后就无法删除了

cls 清屏幕，它后面可以跟着一个参数，清屏之后设置背景的颜色

color – New background color
0 – Black
1 – Blue
2 – Green
3 – Cyan
4 – Red
5 – Magenta
6 – Yellow
7 – Light gray

例如：

cp 拷贝，和DOS下面著名的copy命令一样。它提供了一个参数 -r, 可以用来递归进入目录进行拷贝。简单的说就是你可以用这个参数来copy目录

LZMA 压缩的例子

前一段时间研究了一下 LZ77 算法，后来又看了一下它的改进版本 LZMA。虽然基本思想已经完全领悟，但是要想具体写出代码还是很有难度，直接研究实现算法又被很多细节阻挡。好在时代不同了，虽然你无法写出具体代码，但是也有现成的库供你调用。

目前开源的比较好用的就是 7-zip 了，这里可以看到中文的介绍：http://sparanoid.com/lab/7z/

同时他还提供了 SDK 供以调用 http://sparanoid.com/lab/7z/sdk.html 。

对于 Delphi 的用户，能够使用的 SDK 在 http://www.birtles.org.uk/programming/ 这里可以下载到。是原生的 Delphi 编写无需第三方库。为了测试我编写了一个Console模式下压缩的小程序，并且在程序中我避免使用这个库内部定义的 Stream 而是直接使用 TMemoryStream。

program LZMAencoder;

{$APPTYPE CONSOLE}

{$R *.res}

uses
System.SysUtils, Windows, Classes,ULZMAEncoder,ULZMACommon;

var
FInput,Foutput:TMemoryStream; //直接使用基础的 MemoryStream
encoder:TLZMAEncoder; //编码器
i:integer; //算法方面的要求，最后要补零。具体请查看LZ77描述
begin
FInput:=TMemoryStream.Create; //创建和读取一个文件作为压缩的源
FInput.LoadFromFile('C:\Users\Administrator\Documents\RAD Studio\Projects\LZMAEncoder\original.txt');

encoder:=TLZMAEncoder.Create;

encoder.SetAlgorithm(2); //设置压缩比，看代码似乎没有真正实现
encoder.SetDictionarySize(1 shl 23); //设置字典大小
encoder.SeNumFastBytes(128); //不知道这个是什么
encoder.SetMatchFinder(1); //找到1个匹配
encoder.SetLcLpPb(3, 0, 2); //应该是LZ77算法用到的几个参数
encoder.SetEndMarkerMode(false); //是否写入流结束标志。因为压缩之后的头上有大小
//所以这里完全不用写入
FOutput:=TMemoryStream.Create;
encoder.WriteCoderProperties(FOutput); //写入头信息
for i := 0 to 7 do
WriteByte(FOutput,(FInput.Size shr (8 * i)) and $FF); //补全完整流

encoder.Code(Finput, FOutput, -1, -1); //解压过程
encoder.free;
FOutput.SaveToFile('C:\Users\Administrator\Documents\RAD Studio\Projects\LZMAEncoder\result.7z');
FOutput.Destroy;
Finput.Destroy;
readln;
end.

压缩结果可以直接用 7-zip 打开（WinZip, WinRar不行）。

原始的 LZMA 代码 LZMA.442b

本文提到的例子：LZMAEncoder

Step to UEFI (8)—-显示版本号

UEFI 2.4 SPEC 第四章介绍 EFI System Table 如下

看到其中 Vendor 和 Revision信息便着手写了一个小程序来验证，核心代码如下

EFI_SYSTEM_TABLE	*gST;

//
// Entry point function - ShowVersion
//
EFI_STATUS
EFIAPI
UefiMain (
  IN EFI_HANDLE        ImageHandle,
  IN EFI_SYSTEM_TABLE  *SystemTable
  )
{

  gST = SystemTable;

  Print(L"Firmware Vendor  :  %s \n", gST->FirmwareVendor);
  Print(L"Firmware Revision:  %d \n", gST->FirmwareRevision);

  return EFI_SUCCESS;
}

编译运行之后得到如下结果：

手边暂时没有其他EFI的主板所以没有进一步实验。

下载 ShowVersion