Быстрая проверка на пересечение диапазонов

Тема в разделе "WASM.A&O", создана пользователем HoShiMin, 5 мар 2023.

Метки:
  1. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    Ну, да. Если у нас множество четных и begin == 0x1234567, size == 1, то сразу true... :)

    Множество не непрерывное, а разреженное, между элементами есть пропуски и весь диапазон begin..end может находиться между парой соседних элементов множества не пересекаясь с ними.
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.242
    судя по логике, привязка идёт не к адресу, а к базе..
    MTRR.PhysBase = Addr - Offset = Addr & MTRR.PhysMask // маска просто тупо нулит офсет в верхней части регистра.
     
  3. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    101
    Задача, блин, хрен поймёшь чё надо :)
    Мой вариант:
    1. вычисляем (value & mask). Если (value & mask) > begin + size, то сразу возвращаем 0. Иначе,
    2. интервал чисел [begin, begin + size) заменяем на новый рабочий интервал чисел [begin - (value & mask), begin + size - (value & mask))
    3. Работаем с битами "?". Сначала отбрасываем каждый старший из них, который в одиночку, больше чем begin + size - (value & mask).
    4. Перебираем комбинации оставшихся бит "?", на попадание в интервал чисел [begin - (value & mask), begin + size - (value & mask))
    начинаем с сочетания всех единиц, типа 1__1___11__11, и далее уменьшаем:
    1__1___11__10
    1__1___11__01
    1__1___11__00
    1__1___10__11,
    после каждого шага, проверяем и продолжаем пока, комбинация_бит > begin - (value & mask).
    Ну, ессно, если случится что, комбинация_бит =< begin + size - (value & mask)), возвращаем 1.
    Пожалуй, уменьшать можно ускоренно.
    Сам тестировать не буду :)
     
  4. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    algent,
    Так и сделано в примере выше (только без сдвига диапазона влево) :)
     
  5. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    149
    А не простой ли это перебор - логарифм-то где?
     
  6. rmn

    rmn Well-Known Member

    Публикаций:
    0
    Регистрация:
    23 ноя 2004
    Сообщения:
    2.348
    HoShiMin,
    Можно в начало проверок еще пару шагов с O(1) добавить:
    Код (C):
    1.  
    2. bool intersects (Range* range, type_t begin, type_t end)
    3. {
    4.     type_t minValue, maxValue;
    5.     /*
    6.         За O(1) проверяем варианты:
    7.               [begin  end]
    8.         [Set]
    9.  
    10.               [begin  end]
    11.                            [Set]
    12.  
    13.               [begin  end]
    14.               [    Set   ]
    15.  
    16.         За O(N) (N - количество нулевых бит в маске) проверяем только:
    17.               [begin  end]
    18.             [     Set      ]
    19.     */
    20.     if (range->mask == 0)
    21.         return true;
    22.    
    23.     if (range->mask == ~0)
    24.         return (range->value >= begin && range->value <= end);
    25.        
    26.     minValue = range->value;
    27.     maxValue = range>value | ~range->mask;
    28.    
    29.     if (maxValue < begin || minValue > end)
    30.         return false;
    31.    
    32.     if (begin <= minValue && end >= maxValue)
    33.         return true;
    34.    
    35.     /* дальше тело функции LongTest */
    36.     ...
    37. }
    38.  
     
  7. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    149
    Код (Text):
    1.  000000E9  EB 78                  Jmp    TetrTest
    2. 000000EB            _ForWASM  Proc  Val_Min:Dword,Val_Max:Dword,aStart:Dword,aEnd:Dword
    3. = eSi                ValxMin   Equ eSi
    4. = eDi                ValxMax   Equ eDi
    5.  
    6. 000000EB  55           *        push   ebp
    7. 000000EC  8B EC       *        mov    ebp, esp
    8. 000000EE  8B 75 08            Mov     ValxMin, [Val_Min]  ; ???
    9. 000000F1  8B 7D 0C            Mov     ValxMax, [Val_Max]  ; ???
    10.  
    11. 000000F4  3B 75 14            Cmp     ValxMin, [aEnd]
    12. 000000F7  77 4D            JA     _3
    13. 000000F9  3B 75 10            Cmp     ValxMin, [aStart]
    14. 000000FC  72 43            JB     _2
    15.  
    16. 000000FE  3B 7D 10            Cmp     ValxMax, [aStart]
    17. 00000101  72 43            JB     _3
    18. 00000103  3B 7D 14            Cmp     ValxMax, [aEnd]
    19. 00000106  77 39            JA     _2
    20.  
    21. = eDx                xMsk1    Equ eDx
    22. 00000108  8B D6            Mov     xMsk1, ValxMin  ;;
    23. 0000010A  33 D7            xOr     xMsk1, ValxMax  ;
    24.  
    25.                 ; (aStart And xMsk1) Or  Val_Min в нем (установим возможные 11 из aStart)
    26. 0000010C  8B CA            Mov     eCx, xMsk1    ; ;;;  0111 1111  0111 1111   0111 1110  0111 1110
    27. 0000010E  23 4D 10            And     eCx, [aStart] ; ;;   x011 1111s x010 0000s  x011 1110s x010 0001s
    28.                                           ;      0011 1111  0010 0000   0011 1110  0010 0000
    29. 00000111  0B F1            Or      ValxMin, eCx  ; ;    x000 0000^ x000 0000^  x000 000x^ x000 0000^
    30.                                           ;      x011 1111  x010 0000   x011 111x  x010 000x
    31.                 ; (aEnd   Or NxMsk1) And Val_Max в нем (установим возможные 00 из aEnd)
    32. 00000113  8B CA            Mov     eCx, xMsk1    ; ;;;  0111 1111  0111 1111   0111 1110  0111 1110
    33. 00000115  F7 D1            Not     eCx ;xMsk0    ;      1000 0000  1000 0000   1000 0001  1000 0001
    34. 00000117  0B 4D 14            Or      eCx, [aEnd]   ; ;;   x011 1111e x010 0000e  x011 111xe x010 000xe
    35.                                           ;      1011 1111  1010 0000   1011 1111  1010 0001
    36. 0000011A  23 F9            And     ValxMax, eCx  ; ;    x111 1111v x111 1111v  x111 111xv x111 111xv
    37.                                           ;      x011 1111  x010 0000   x011 111x  x010 000x
    38.                 ; Одинаковые биты в ValxMin и ValxMax не надо обрабатывать - как 00 в xMsk1!
    39. 0000011C  8B D6            Mov     xMsk1, ValxMin  ;;
    40. 0000011E  33 D7            xOr     xMsk1, ValxMax  ;
    41.                 ; Microsoft
    42. 00000120             _1:
    43. 00000120  0F BD CA            BSR     eCx, xMsk1
    44. 00000123  74 26            JZ     _4
    45. 00000125  8B DE            Mov     eBx, ValxMin
    46. 00000127  0F B3 CA            BT_c    xMsk1, eCx
    47. 0000012A  0F AB CB            BT_s    eBx, eCx
    48. 0000012D  39 5D 10            Cmp     [aStart], eBx
    49. 00000130  0F 47 F3           cMovA    ValxMin, eBx              ; ..1000  ..0000
    50. 00000133  0F 97 C5            SetA     Ch           ; 0 1 0
    51. 00000136  39 5D 14            Cmp     [aEnd], eBx
    52. 00000139  0F 42 FB           cMovB    ValxMax, eBx  ; 1 0 0     ; ..1111  ..1000
    53. 0000013C  0F 93 C1            SetAE    Cl           ; 0 1 1
    54. 0000013F  E2 DF            LoopD  _1
    55. 00000141             _2:        ; Found
    56. 00000141  F9                StC
    57.                     Ret
    58. 00000142  C9           *        leave
    59. 00000143  C2 0010       *        ret    00010h
    60. 00000146             _3:        ; NotFound
    61. 00000146  F8                ClC
    62.                     Ret
    63. 00000147  C9           *        leave
    64. 00000148  C2 0010       *        ret    00010h
    65. 0000014B             _4:        ;  Тестовая проверка
    66. 0000014B  3B F7            Cmp     ValxMin, ValxMax
    67. 0000014D  0F 87 00000095        JA      Err
    68. 00000153  3B 75 10            Cmp     ValxMin, [aStart]
    69. 00000156  0F 93 C5            SetAE    Ch             ; 0 1 0 1
    70. 00000159  3B 7D 14            Cmp     ValxMax, [aEnd] ;
    71. 0000015C  0F 96 C1            SetBE    Cl             ; 1 0 0 1
    72. 0000015F  E3 E5            JeCxZ  _3
    73. 00000161  EB DE            Jmp    _2
    74. 00000163            _ForWASM  EndP
    75.                 ;
    76. 00000163             TetrTest:
    77. 00000163  0F 31                               RdTSC        ; > eDx:eAx
    78. 00000165  A3 00004090 R                        Mov  testTime0,eAx  ; сохранение TSC
    79. 0000016A  89 15 00004094 R                        Mov  testTime0+4,eDx  ;
    80. 00000170  FC                    ClD
    81. 00000171  33 C0                xOr  eAx,eAx
    82. 00000173  BF 00000030 R            Mov  eDi,of_[BS]
    83. 00000178  B9 00000800                Mov  eCx,10000h / 8 / 4
    84. 0000017D  F3/ AB           rep  StosD ; [ds:eDi]
    85.  
    86. 0000017F  B8 0000FFFF              Mov  eAx,0FFFFh                                  ;
    87. 00000184               _CklTest:                                           ;
    88. 00000184  0F B6 CC              MovZx  eCx,Ah  ; .AdrStart Size                  ;
    89. 00000187  89 0D 0000403C R          Mov    [AdrEnd],eCx                              ;
    90. 0000018D  83 25 0000403C R          And    [AdrEnd],0Fh ; Size                       ;
    91.        0F
    92. 00000194  C1 E9 04              SHR    eCx,4                                     ;
    93. 00000197  89 0D 00004038 R          Mov    [AdrStart],eCx                            ;
    94. 0000019D  01 0D 0000403C R          Add    [AdrEnd],eCx ; Это может быть 15+15 Мах   ;
    95.                                                                        ;
    96. 000001A3  0F B6 F0              MovZx  eSi,Al  ; .xMsk0 Value                    ;
    97. 000001A6  8B FE              Mov    eDi,eSi                                   ;
    98. 000001A8  83 E6 0F              And    eSi,0Fh ; Value                           ;
    99. 000001AB  C1 EF 04              SHR    eDi,4   ; xMsk0                           ;
    100. 000001AE  23 F7              And    eSi,eDi                                   ;
    101. 000001B0  F7 D7              Not    eDi     ; xMsk1                           ;
    102. 000001B2  0B FE              Or     eDi,eSi                                   ;
    103.  
    104.                 ;     Mov  eAx,0FFFFFFFFh                              ;
    105.                 ;  _CklTest:                                           ;
    106.                 ;     MovZx  eCx,Ah  ; .AdrStart Size                  ;
    107.                 ;     Mov    [AdrStart],eCx                            ;
    108.                 ;     Mov    [AdrEnd],eCx                              ;
    109.                 ;     MovZx  eCx,Al  ; Size                            ;
    110.                 ;     Add    [AdrEnd],eCx                              ;
    111.                 ;                                                      ;
    112.                 ;     ROR    eAx,16                                    ;
    113.                 ;     MovZx  eSi,Al  ; Value                           ;
    114.                 ;     MovZx  eDi,Ah  ; xMsk0                           ;
    115.                 ;     And    eSi,eDi                                   ;
    116.                 ;     Not    eDi     ; xMsk1                           ;
    117.                 ;     Or     eDi,eSi                                   ;
    118.                 ;     ROL    eAx,16                                    ;
    119.  
    120.                  invokeXP _ForWASM ,eSi,eDi,AdrStart,AdrEnd
    121. 000001B4  FC             1                ClD
    122.                  1  
    123. 000001B5  FF 35 0000403C R *        push   AdrEnd
    124. 000001BB  FF 35 00004038 R *        push   AdrStart
    125. 000001C1  57           *        push   edi
    126. 000001C2  56           *        push   esi
    127. 000001C3  E8 FFFFFF23       *        call   _ForWASM
    128.                  1     invoke   _ForWASM,eSi,eDi,AdrStart,AdrEnd
    129. 000001C8  73 07                JNC NotFound
    130. 000001CA  0F AB 05                BT_s D_[BS],eAx  ; бит карта 1=есть
    131.        00000030 R
    132. 000001D1             NotFound:
    133. 000001D1  48                    Dec  eAx
    134.                      ;  JNL  _CklTest
    135. 000001D2  75 B0                JNZ  _CklTest
    136.  
    --- Сообщение объединено, 11 мар 2023 ---
    ; Как отлаживаться-тo. И ускоритель этот у меня не убыстряет.
     
    Последнее редактирование: 11 мар 2023
  8. algent

    algent Member

    Публикаций:
    0
    Регистрация:
    11 апр 2018
    Сообщения:
    101
    А я смотрю у HoShiMin`а чё то не запускается, не отлаживается и решил, что тема ещё актуальна.

    Я или пропустил, или поленился в самом начале поставить:
    if (size >= mask)
    return true;
    а уж детально вникать какой вариант из нескольких, наилучший, этот подвиг не для меня :)
     
  9. HoShiMin

    HoShiMin Well-Known Member

    Публикаций:
    5
    Регистрация:
    17 дек 2016
    Сообщения:
    1.454
    Адрес:
    Россия, Нижний Новгород
    algent нравится это.
  10. R81...

    R81... Active Member

    Публикаций:
    0
    Регистрация:
    1 фев 2020
    Сообщения:
    149
    • Если надо - помнится тестировал, но вторично вникать не буду.
    • Код (ASM):
      1.  TetrTest:
      2.                        RdTSC        ; > eDx:eAx
      3.                     Mov  testTime0,eAx  ; сохранение TSC
      4.                     Mov  testTime0+4,eDx  ;
      5.         ClD
      6.         xOr  eAx,eAx
      7.         Mov  eDi,of_[BS]
      8.         Mov  eCx,10000h / 8 / 4
      9.    rep  StosD ; [ds:eDi]
      10.  
      11.       Mov  Cnt,0FFFFFFFFh  ; 0.071.017.920 uS  E8400   ;
      12.    _CklTest:               ; =.../2FF37A00h            ;
      13.       MovZx  eCx,B_[Cnt+1]  ; .AdrStart                ;
      14.       Mov    [AdrStart],eCx                            ;
      15.       Mov    [AdrEnd],eCx                              ;
      16.       MovZx  eCx,B_[Cnt]    ; Size                     ;
      17.       Add    [AdrEnd],eCx   ; может быть 255+255 Max   ;
      18.       Mov    [iSize], eCx                              ;
      19.       Inc    eCx                                       ;
      20.       Mov    [iQnt], eCx                               ;
      21.                                                        ;
      22.       MovZx  eSi,B_[Cnt+2]  ; Value                    ;
      23.       MovZx  eDi,B_[Cnt+3]  ; Msk0x                    ;
      24.       Mov    [Msk0x],eDi                               ;
      25.       And    eSi,eDi                                   ;
      26.       xOr    eDi,255        ; Msk1x  13.03.23          ;
      27.       Mov    [Msk1x],eDi                               ;
      28.       Or     eDi,eSi                                   ;
      29.  
      30. ;   ;          0001000000000000                        ;
      31. ;   ; Mov  Cnt,1010000010011001y                       ;
      32. ;   ;              0000    1001                        ;
      33. ;   ;          1010    1001                            ;
      34. ;   ;          <St><Sz><Vl><Ms>                        ;
      35. ;   ;                      0110                        ;
      36. ;     Mov  Cnt,0FFFFh   ; SMV  память  MVS           ;
      37. ;  _CklTest:                                           ;
      38. ;     MovZx  eCx, B_[Cnt+1]  ; .AdrStart Size          ;
      39. ;     Mov    eAx, eCx                                  ;
      40. ;     And    eAx, 0Fh                                  ;
      41. ;     Mov    [iSize], eAx                              ;
      42. ;     SHR    eCx, 4                                    ;
      43. ;     Mov    [AdrStart], eCx                           ;
      44. ;     Add    eCx, eAx                                  ;
      45. ;     Mov    [AdrEnd], eCx  ; Это может быть 15+15 Мах ;
      46. ;     Inc    eAx                                       ;
      47. ;     Mov    [iQnt], eAx                               ;
      48. ;                                                      ;
      49. ;     MovZx  eSi,B_[Cnt]   ; Msk0x Value               ;
      50. ;     Mov    eDi,eSi                                   ;
      51. ;     SHR    eDi,4         ; Msk0x                     ;
      52. ;     Mov    [Msk0x],eDi                               ;
      53. ;     And    eSi,eDi       ; Val_Min                   ;
      54. ;     xOr    eDi,0Fh       ; Msk1x  13.03.23           ;
      55. ;     Mov    [Msk1x],eDi                               ;
      56. ;     Or     eDi,eSi       ; Val_Max                   ;
      57.  
      58. invokeXP _ForWASM,eSi,eDi,AdrStart,AdrEnd
      59.  
      60. ;       Mov [Found],0        ; oooo
      61. ;       JNC NotFound         ;
      62. ;       Mov [Found], 1       ; oooo
      63. ;       Mov eCx, [Cnt]       ;
      64. ;       BT_s D_[BS], eCx     ; бит карта 1=есть
      65. ;  NotFound:                 ;
      66.         MovZx  eCx, [qIter]       ;
      67.         Add    [qIterAll], eCx    ;
      68.     Mov [AdrExit],$               ; oooo
      69.     JL  DiagnoseExit              ; oooo
      70.         Cmp     Cl, [qIterMax]    ;
      71.        cMovL   eCx, D_[qIterMax]  ; oooo
      72.         Mov    [qIterMax], Cl     ;
      73.  
      74.         Dec  Cnt
      75.    ;    JNL  _CklTest   ;
      76.         JNZ  _CklTest  ;
      77.  
      78.   Call _TimeConsole
      79.  
      80.         Mov [AdrExit],$   ; oooo
      81.         Jmp DiagnoseExit  ; oooo
      82. ;
      83. ;
      84. ;
      85. _ForWASM  Proc  Val_Min:Dword,Val_Max:Dword,aStart:Dword,aEnd:Dword
      86.     Mov     [qIter], 0  ; oooo
      87.  
      88.     Mov     eSi, [Val_Min]  ; ??
      89.     Mov     eDi, [Val_Max]  ; ??
      90.  
      91.     Cmp     eSi, [aEnd]
      92.     JA     _3
      93.     Cmp     eSi, [aStart]
      94.     JAE    _2
      95.  
      96.     Cmp     eDi, [aStart]
      97.     JB     _3
      98.     Cmp     eDi, [aEnd]
      99.     JBE    _2
      100.  
      101. ;   Ret   ;  0.056.045.076 uS  E8400
      102.  
      103.  
      104.     Sub     [aEnd], eSi    ;;;;
      105.     Sub     eDi, eSi       ;;;
      106.     Sub     [aStart], eSi  ;;
      107.     xOr     eSi, eSi       ; упрощает (см. _6: /.../   JZ     _2), скорость?
      108.  
      109.     Mov     eDx, [Msk1x]
      110.  
      111.   ; Inc     [qIterAll]  ;  без  этого Inc после /????
      112.     Mov     eCx, [iQnt]
      113.     Cmp     eCx, 3   ; 3 =26E0/03E0  можно выбрать другое < qIter
      114.     JBE    _5
      115.  
      116.     BSR     eAx, eDx  ;  =3BF0/18F0 1.320 uS  без этого  всего =3980 1.326 uS
      117.     xOr     eBx,eBx
      118.     Inc     eAx       ;;
      119.     BT_s    eBx, eAx  ; старая .1... Msk1x * 2
      120.     Sub     eBx,eDx   ; Наибольший Void
      121.     Cmp     eBx, [iQnt]
      122.     JBE    _2         ; <= qnt
      123.  
      124.     Mov     [qIterMax+4],1  ; oooo
      125. ; Microsoft
      126. _1:
      127.     BSR     eCx, eDx
      128.   ; BSF     eCx, eDx  ; Так ошибки
      129.     JZ     _3         ; ../Test_Ou4.ttr
      130.     Inc     [qIter]     ; oooo
      131.     Mov     eBx, eSi
      132.     BT_c    eDx, eCx
      133.     BT_s    eBx, eCx
      134. ;  BT_n    eBx, eCx
      135.     Cmp     [aStart], eBx
      136.    cMovA    eSi, eBx
      137.     SetA     Ch           ; 0 1 0
      138.     Cmp     [aEnd], eBx
      139.    cMovB    eDi, eBx      ; 1 0 0
      140.     SetAE    Cl           ; 0 1 1
      141.     LoopD  _1
      142. _2:        ; Found
      143.     StC
      144.     Ret
      145. _5:
      146.     Mov     eAx, [aStart]
      147. _6:      ; В общем случае iSize/2 не поможет
      148.     Mov     eBx, eAx
      149.     And     eBx, [Msk0x]
      150.     JZ     _2
      151.     Inc     eAx
      152.     LoopD  _6
      153. _3:        ; NotFound
      154.     ClC
      155.     Ret
      156. _ForWASM  EndP
      157. ; Microsoft
      158.