Simatic Step 7. STL. Подсчет установленных бит.

PLC
  Эта функция возвращает кол-во установленных (единичных) бит в аргументе. Иногда возвращаемое значение называют весом Хемминга. Кроме самостоятельной ценности, по возвращаемому значению функции легко определить четность аргумента (нулевой бит).

В стандартной библиотеке уже есть функция FC99 «BITSUM» для этой цели.

FUNCTION "BITSUM" : INT
TITLE = BITSUM (Sum Number of Bits)
AUTHOR : SEA
FAMILY : CONVERT
NAME : BITSUM
VERSION : 2.0

VAR_INPUT
  IN : DWORD ;	
END_VAR

VAR_TEMP
  wrkVal : DWORD ;	
END_VAR

BEGIN
NETWORK
TITLE =

  L     0; 		// set default RET_VAL
  T     #RET_VAL; 	// .
  L     #IN; 		// for(wrk = in; wrk <> 0; wrk >>= 1)
  T     #wrkVal; 	// {
A001: 
  L     0; 		//   if(wrk == 0) break;
  L     #wrkVal; 	//   .
  ==D   ; 		//   .
  JC    A002; 		//   .
  SRD   1; 		//   wrk >>= 1
  T     #wrkVal; 	//   .
  JZ    A001; 		//   if(LSB == 0) continue;
  L     #RET_VAL; 	//   RET_VAL++
  L     1; 		//   .
  +I    ; 		//   .
  T     #RET_VAL; 	//   .
  JU    A001; 		// }
A002: 
  SET   ; 		// set BR
  SAVE  ; 		// 
  
END_FUNCTION

  Алгоритм работы основан на последовательном переборе бит в цикле с подсчетом установленных. Это не самый быстрый алгоритм.
Одним из самых быстрых считается алгоритм бинарного поиска, его реализация на С:

  x = (x & 0x55555555) + (x & 0xAAAAAAAA) >> 1;
  x = (x & 0x33333333) + (x & 0xCCCCCCCC) >> 2;
  x = (x & 0x0F0F0F0F) + (x & 0xF0F0F0F0) >> 4;
  x = (x & 0x00FF00FF) + (x & 0xFF00FF00) >> 8;
  x = (x & 0x0000FFFF) + (x & 0xFFFF0000) >> 16;

Его реализация на STL при расчетах использует только внутренние регистры:

FUNCTION FC10: VOID	

TITLE = "Подсчет кол-ва единичных бит"

AUTHOR:   Anakost       // 
FAMILY:   SOHO   	//
NAME:     BitTotal      //  
VERSION:  1.0    	//

VAR_INPUT            
  INPUT: DWORD;    
END_VAR

VAR_OUTPUT            
  OUTPUT: BYTE;
END_VAR

BEGIN

NETWORK
TITLE = Алгоритм бинарного поиска для DWORD

  L #INPUT;
// x = (x & 0x55555555) + (x & 0xAAAAAAAA) >> 1;
  PUSH;			// копия ACCU1 в ACCU2
  AD DW#16#55555555;	// ACCU1 and 0x55555555
  TAK;			// ACCU1 <-> ACCU2
  AD DW#16#AAAAAAAA;	// ACCU1 and 0xAAAAAAAA
  SRD 1;		// ACCU1 >> 1
  +D;			// ACCU1 <- ACCU1 + ACCU2
// x = (x & 0x33333333) + (x & 0xCCCCCCCC) >> 2;
  PUSH;			//
  AD DW#16#33333333;	//
  TAK;			//
  AD DW#16#CCCCCCCC;	//
  SRD 2;	        //
  +D;			//
// x = (x & 0x0F0F0F0F) + (x & 0xF0F0F0F0) >> 4;
  PUSH;			//
  AD DW#16#0F0F0F0F;	//
  TAK;			//
  AD DW#16#F0F0F0F0;	//
  SRD 4;		//
  +D;			//
// x = (x & 0x00FF00FF) + (x & 0xFF00FF00) >> 8;
  PUSH;			//
  AD DW#16#00FF00FF;	//
  TAK;			//
  AD DW#16#FF00FF00;	//
  SRD 8;		//
  +D;			//
// x = (x & 0x0000FFFF) + (x & 0xFFFF0000) >> 16;
  PUSH;			//
  AD DW#16#0000FFFF;	//
  TAK;			//
  AD DW#16#FFFF0000;	//
  SRD 16;		//
  +D;			//
//-----------------------
  T #OUTPUT;		//
  
END_FUNCTION

  Если входная величина ограничена словом WORD, алгоритм можно упростить (не нужна последняя строчка):

VAR_INPUT            
  INPUT: WORD;    
END_VAR
...
NETWORK
TITLE = Алгоритм бинарного поиска для WORD

  L #INPUT;
// x = (x & 0x5555) + (x & 0xAAAA) >> 1;
  PUSH;			// копия ACCU1 в ACCU2
  AW W#16#5555;	        // ACCU1 and 0x5555
  TAK;			// ACCU1 <-> ACCU2
  AW W#16#AAAA;	        // ACCU1 and 0xAAAA
  SRW 1;		// ACCU1 >> 1
  +I;			// ACCU1 <- ACCU1 + ACCU2
// x = (x & 0x3333) + (x & 0xCCCC) >> 2;
  PUSH;			//
  AW W#16#3333;	        //
  TAK;			//
  AW W#16#CCCC;	        //
  SRW 2;		//
  +I;			//
// x = (x & 0x0F0F) + (x & 0xF0F0) >> 4;
  PUSH;			//
  AW W#16#0F0F;	        //
  TAK;			//
  AW W#16#F0F0;	        //
  SRW 4;		//
  +I;			//
// x = (x & 0x00FF) + (x & 0xFF00) >> 8;
  PUSH;			//
  AW W#16#00FF;	        //
  TAK;			//
  AW W#16#FF00;	        //
  SRW 8;		//
  +I;			//
//-----------------
  T #OUTPUT;		//

Если же входная величина ограничена BYTE, можно убрать еще одну строчку:

VAR_INPUT            
  INPUT: BYTE;    
END_VAR
...
NETWORK
TITLE = Алгоритм бинарного поиска для BYTE

  L #INPUT;
// x = (x & 0x55) + (x & 0xAA) >> 1;
  PUSH;		    // копия ACCU1 в ACCU2
  AW B#16#55;	    // ACCU1 and 0x55
  TAK;		    // ACCU1 <-> ACCU2
  AW B#16#AA;	    // ACCU1 and 0xAA
  SRW 1;	    // ACCU1 >> 1
  +I;		    // ACCU1 <- ACCU1 + ACCU2
// x = (x & 0x33) + (x & 0xCC) >> 2;
  PUSH;		    //
  AW B#16#33;	    //
  TAK;		    //
  AW B#16#CC;	    //
  SRW 2;	    //
  +I;		    //
// x = (x & 0x0F) + (x & 0xF0) >> 4;
  PUSH;		    //
  AW B#16#0F;	    //
  TAK;		    //
  AW B#16#F0;	    //
  SRW 4;	    //
  +I;		    //
//-----------------
  T #OUTPUT;	    //


P.S. В книге Генри Уорена «Алгоритмические трюки для программистов», 2014 г. приведен более оптимизированный вариант алгоритма бинарного поиска:

  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x + (x >> 4)) & 0x0F0F0F0F;
  x = x + (x >> 8);
  x = (x + (x >> 16)) & 0x0000003F;

Соответствующий ему код на STL:

FUNCTION FC10: VOID	

TITLE = "Подсчет кол-ва единичных бит"

AUTHOR:   Anakost       // 
FAMILY:   SOHO   	//
NAME:     BitTotal      //  
VERSION:  1.0    	//

VAR_INPUT            
  INPUT: DWORD;    
END_VAR

VAR_OUTPUT            
  OUTPUT: BYTE;
END_VAR

BEGIN

NETWORK
TITLE = Алгоритм бинарного поиска FastDWORD

  L #INPUT;
// x = x - ((x >> 1) & 0x55555555);
  PUSH;			//
  SRD 1;		//
  AD DW#16#55555555;	//
  -D;			//
// x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  PUSH;			//
  SRD 2;		//
  AD DW#16#33333333;	//
  TAK;			//
  AD DW#16#33333333;	//
  +D;			//
// x = (x + (x >> 4)) & 0x0F0F0F0F;
  PUSH;			//
  SRD 4;		//
  +D;			//
  AD DW#16#0F0F0F0F;	//
// x = x + (x >> 8);
  PUSH;			//
  SRD 8;	        //
  +D;			//
// x = (x + (x >> 16)) & 0x0000003F;
  PUSH;			//
  SRD 16;		//
  +D;			//
  AD DW#16#0000003F;	//
//-----------------
  T #OUTPUT;	        //
  
END_FUNCTION

  • 0
  • 09 декабря 2016, 19:06
  • anakost

Комментарии (0)

RSS свернуть / развернуть
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.