Subversion Repositories Kolibri OS

Rev

Rev 3681 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

  1. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2. ;;                                                              ;;
  3. ;; Copyright (C) KolibriOS team 2004-2015. All rights reserved. ;;
  4. ;; Distributed under terms of the GNU General Public License    ;;
  5. ;;                                                              ;;
  6. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  7.  
  8. $Revision: 5363 $
  9.  
  10.  
  11. ; Small heap based on malloc/free/realloc written by Doug Lea
  12. ; Version 2.8.3 Thu Sep 22 11:16:15 2005  Doug Lea  (dl at gee)
  13. ; Source ftp://gee.cs.oswego.edu/pub/misc/malloc.c
  14. ; License http://creativecommons.org/licenses/publicdomain.
  15.  
  16.  
  17. ; eax= size
  18.  
  19. ; temp
  20. ;  esi= nb
  21. ;  ebx= idx
  22. ;
  23. align 4
  24. malloc:
  25.         push    ebx esi
  26.  
  27. ; nb = ((size+7)&~7)+8;
  28.  
  29.         mov     esi, eax   ;size
  30.         add     esi, 7
  31.         and     esi, -8
  32.         add     esi, 8
  33.  
  34.         mov     ecx, mst.mutex
  35.         call    mutex_lock
  36.  
  37.         cmp     esi, 256
  38.         jae     .large
  39.  
  40.         mov     ecx, esi
  41.         shr     ecx, 3
  42.         or      eax, -1
  43.         shl     eax, cl
  44.         and     eax, [mst.smallmap]
  45.         jz      .small
  46.  
  47.         push    ebp
  48.         push    edi
  49.  
  50.         bsf     eax, eax
  51.         mov     ebx, eax
  52.  
  53. ; psize= idx<<3;
  54. ; B = &ms.smallbins[idx];
  55. ; p = B->fd;
  56. ; F = p->fd;
  57. ; rsize= psize-nb;
  58.  
  59.         lea     ebp, [eax*8]              ;ebp= psize
  60.         shl     eax, 4
  61.         lea     edi, [mst.smallbins+eax]  ;edi= B
  62.         mov     edx, [edi+8]              ;edx= p
  63.         mov     eax, [edx+8]              ;eax= F
  64.         mov     ecx, ebp
  65.         sub     ecx, esi                  ;ecx= rsize
  66.  
  67. ; if (B == F)
  68.         cmp     edi, eax
  69.         jne     @F
  70.  
  71.         btr     [mst.smallmap], ebx
  72. @@:
  73.  
  74. ; B->fd = F;
  75. ; F->bk = B;
  76. ; if(rsize<16)
  77.  
  78.         cmp     ecx, 16
  79.         mov     [edi+8], eax
  80.         mov     [eax+12], edi
  81.         jae     .split
  82.  
  83. ; p->head = psize|PINUSE_BIT|CINUSE_BIT;
  84. ; (p + psize)->head |= PINUSE_BIT;
  85.  
  86.         lea     eax, [edx+8]
  87.         or      dword [edx+ebp+4], 1
  88.  
  89.         or      ebp, 3
  90.         mov     [edx+4], ebp
  91.  
  92.         pop     edi
  93.         pop     ebp
  94. .done:
  95.         mov     esi, eax
  96.         mov     ecx, mst.mutex
  97.         call    mutex_unlock
  98.         mov     eax, esi
  99.         pop     esi ebx
  100.         ret
  101.  
  102. .split:
  103.         lea     ebx, [edx+8]              ;ebx=mem
  104.  
  105. ; r = chunk_plus_offset(p, nb);
  106. ; p->head = nb|PINUSE_BIT|CINUSE_BIT;
  107. ; r->head = rsize|PINUSE_BIT;
  108.  
  109.         lea     eax, [edx+esi]            ;eax= r
  110.         or      esi, 3
  111.         mov     [edx+4], esi
  112.  
  113.         mov     edx, ecx
  114.         or      edx, 1
  115.         mov     [eax+4], edx
  116.  
  117. ; (r + rsize)->prev_foot = rsize;
  118.  
  119.         mov     [eax+ecx], ecx
  120.  
  121. ; I  = rsize>>3;
  122.  
  123.         shr     ecx, 3
  124.  
  125. ;      ms.smallmap |=  1<< I;
  126.         bts     [mst.smallmap], ecx
  127.  
  128. ; B = &ms.smallbins[I];
  129.  
  130.         shl     ecx, 4
  131.         pop     edi
  132.         pop     ebp
  133.         add     ecx, mst.smallbins        ;ecx= B
  134.  
  135.         mov     edx, [ecx+8]              ; F = B->fd;
  136.         mov     [ecx+8], eax              ; B->fd = r;
  137.         mov     [edx+12], eax             ; F->bk = r;
  138.         mov     [eax+8], edx              ; r->fd = F;
  139.         mov     [eax+12], ecx             ; r->bk = B;
  140.  
  141.         mov     eax, ebx
  142.         jmp     .done
  143.  
  144. .small:
  145.  
  146. ; if (ms.treemap != 0 && (mem = malloc_small(nb)) != 0)
  147. ;;;;;;;;;;; start a change <lrz>
  148.         mov     eax, [mst.treemap]
  149.         test    eax, eax
  150. ;;;;;;;;;;; end the change <lrz>
  151. ;           cmp [mst.treemap], 0
  152.         jz      .from_top
  153.         mov     eax, esi
  154.         call    malloc_small
  155.         test    eax, eax
  156.         jz      .from_top
  157.         jmp     .done
  158.  
  159. .large:
  160.  
  161. ; if (ms.treemap != 0 && (mem = malloc_large(nb)) != 0)
  162.  
  163.         cmp     [mst.treemap], 0
  164.         je      .from_top
  165.  
  166.         call    malloc_large  ;esi= nb
  167.         test    eax, eax
  168.         jne     .done
  169. .from_top:
  170.  
  171. ; if (nb < ms.topsize)
  172.  
  173.         mov     eax, [mst.topsize]
  174.         cmp     esi, eax
  175.         jae     .fail
  176.  
  177. ; rsize = ms.topsize -= nb;
  178. ; p = ms.top;
  179.  
  180.         mov     ecx, [mst.top]
  181.         sub     eax, esi
  182.         mov     [mst.topsize], eax
  183.  
  184. ; r = ms.top = chunk_plus_offset(p, nb);
  185. ; r->head = rsize | PINUSE_BIT;
  186. ; p->head = nb |PINUSE_BIT|CINUSE_BIT;
  187.  
  188.         lea     edx, [ecx+esi]
  189.         or      eax, 1
  190.         mov     [mst.top], edx
  191.         or      esi, 3
  192.         mov     [edx+4], eax
  193.         mov     [ecx+4], esi
  194.         lea     eax, [ecx+8]
  195.         jmp     .done
  196.  
  197. .fail:
  198.         xor     eax, eax
  199.         jmp     .done
  200.  
  201. ; param
  202. ;  eax= mem
  203. align 4
  204. free:
  205.         test    eax, eax
  206.         jz      .exit
  207.  
  208.         push    ebx edi
  209.         mov     edi, eax
  210.         add     edi, -8
  211.  
  212. ; if(p->head & CINUSE_BIT)
  213.  
  214.         test    byte [edi+4], 2
  215.         je      .fail
  216.  
  217.         mov     ecx, mst.mutex
  218.         call    mutex_lock
  219.  
  220. ; psize = p->head & (~3);
  221.  
  222.         mov     eax, [edi+4]
  223.         push    esi
  224.         mov     esi, eax
  225.         and     esi, -4
  226.  
  227. ; next = chunk_plus_offset(p, psize);
  228. ; if(!(p->head & PINUSE_BIT))
  229.  
  230.         test    al, 1
  231.         lea     ebx, [esi+edi]
  232.         jne     .next
  233.  
  234. ; prevsize = p->prev_foot;
  235. ; prev=p - prevsize;
  236. ; psize += prevsize;
  237. ; p = prev;
  238.  
  239.         mov     ecx, [edi] ;ecx= prevsize
  240.         add     esi, ecx             ;esi= psize
  241.         sub     edi, ecx             ;edi= p
  242.  
  243. ; if (prevsize < 256)
  244.  
  245.         cmp     ecx, 256
  246.         jae     .unlink_large
  247.  
  248.         mov     eax, [edi+8]         ;F = p->fd;
  249.         mov     edx, [edi+12]        ;B = p->bk;
  250.  
  251. ; if (F == B)
  252. ; ms.smallmap &=  ~(1<< I);
  253.         shr     ecx, 3
  254.         cmp     eax, edx
  255.         jne     @F
  256.         btr     [mst.smallmap], ecx
  257. @@:
  258.         mov     [eax+12], edx          ;F->bk = B;
  259.         mov     [edx+8], eax           ;B->fd = F
  260.         jmp     .next
  261. .unlink_large:
  262.         mov     edx, edi
  263.         call    unlink_large_chunk
  264. .next:
  265.  
  266. ; if(next->head & PINUSE_BIT)
  267.  
  268.         mov     eax, [ebx+4]
  269.         test    al, 1
  270.         jz      .fail2
  271.  
  272. ; if (! (next->head & CINUSE_BIT))
  273.  
  274.         test    al, 2
  275.         jnz     .fix_next
  276.  
  277. ; if (next == ms.top)
  278.  
  279.         cmp     ebx, [mst.top]
  280.         jne     @F
  281.  
  282. ; tsize = ms.topsize += psize;
  283.  
  284.         mov     eax, [mst.topsize]
  285.         add     eax, esi
  286.         mov     [mst.topsize], eax
  287.  
  288. ; ms.top = p;
  289. ; p->head = tsize | PINUSE_BIT;
  290.  
  291.         or      eax, 1
  292.         mov     [mst.top], edi
  293.         mov     [edi+4], eax
  294. .fail2:
  295.         mov     esi, eax
  296.         mov     ecx, mst.mutex
  297.         call    mutex_unlock
  298.         mov     eax, esi
  299.         pop     esi
  300. .fail:
  301.         pop     edi ebx
  302. .exit:
  303.         ret
  304.  
  305. @@:
  306.  
  307. ; nsize = next->head & ~INUSE_BITS;
  308.  
  309.         and     eax, -4
  310.         add     esi, eax               ;psize += nsize;
  311.  
  312. ; if (nsize < 256)
  313.  
  314.         cmp     eax, 256
  315.         jae     .unl_large
  316.  
  317.         mov     edx, [ebx+8]           ;F = next->fd
  318.         mov     ebx, [ebx+12]          ;B = next->bk
  319.  
  320. ; if (F == B)
  321.  
  322.         cmp     edx, ebx
  323.         jne     @F
  324.         mov     ecx, eax
  325.         shr     ecx, 3
  326.         btr     [mst.smallmap], ecx
  327. @@:
  328.         mov     [edx+12], ebx          ;F->bk = B
  329.  
  330. ; p->head = psize|PINUSE_BIT;
  331.  
  332.         mov     ecx, esi
  333.         mov     [ebx+8], edx
  334.         or      ecx, 1
  335.         mov     [edi+4], ecx
  336.  
  337. ; (p+psize)->prev_foot = psize;
  338.  
  339.         mov     [esi+edi], esi
  340.  
  341. ; insert_chunk(p,psize);
  342.  
  343.         mov     eax, esi
  344.         mov     ecx, edi
  345.         call    insert_chunk
  346.         jmp     .fail2
  347. .unl_large:
  348.  
  349. ; unlink_large_chunk((tchunkptr)next);
  350.  
  351.         mov     edx, ebx
  352.         call    unlink_large_chunk
  353. ; p->head = psize|PINUSE_BIT;
  354.  
  355.         mov     ecx, esi
  356.         or      ecx, 1
  357.         mov     [edi+4], ecx
  358.  
  359. ; (p+psize)->prev_foot = psize;
  360.  
  361.         mov     [esi+edi], esi
  362.  
  363. ; insert_chunk(p,psize);
  364.  
  365.         mov     eax, esi
  366.         mov     ecx, edi
  367.         call    insert_chunk
  368.         jmp     .fail2
  369. .fix_next:
  370.  
  371. ; (p+psize)->prev_foot = psize;
  372. ; next->head &= ~PINUSE_BIT;
  373. ; p->head = psize|PINUSE_BIT;
  374.  
  375.         and     eax, -2
  376.         mov     edx, esi
  377.         mov     [ebx+4], eax
  378.         or      edx, 1
  379.         mov     [edi+4], edx
  380.  
  381. ; (p+psize)->prev_foot = psize;
  382.  
  383.         mov     [esi+edi], esi
  384. ; insert_chunk(p,psize);
  385.  
  386.         mov     eax, esi
  387.         mov     ecx, edi
  388.         call    insert_chunk
  389.         jmp     .fail2
  390.  
  391. ; param
  392. ;  ecx = chunk
  393. ;  eax = size
  394.  
  395. insert_chunk:
  396.  
  397.         cmp     eax, 256
  398.         push    esi
  399.         mov     esi, ecx
  400.         jae     .large
  401.  
  402. ; I  = S>>3;
  403. ; ms.smallmap |=  1<< I;
  404.  
  405.         shr     eax, 3
  406.         bts     [mst.smallmap], eax
  407.  
  408. ; B = &ms.smallbins[I];
  409.  
  410.         shl     eax, 4
  411.         add     eax, mst.smallbins
  412.         mov     edx, [eax+8]           ;F = B->fd
  413.         mov     [eax+8], esi           ;B->fd = P
  414.         mov     [edx+12], esi          ;F->bk = P
  415.         mov     [esi+8], edx           ;P->fd = F
  416.         mov     [esi+12], eax          ;P->bk = B
  417.         pop     esi
  418.         ret
  419. .large:
  420.         mov     ebx, eax
  421.         call    insert_large_chunk
  422.         pop     esi
  423.         ret
  424.  
  425.  
  426. ; param
  427. ;  esi= chunk
  428. ;  ebx= size
  429.  
  430. insert_large_chunk:
  431.  
  432. ; I = compute_tree_index(S);
  433.  
  434.         mov     edx, ebx
  435.         shr     edx, 8
  436.         bsr     eax, edx
  437.         lea     ecx, [eax+7]
  438.         mov     edx, ebx
  439.         shr     edx, cl
  440.         and     edx, 1
  441.         lea     ecx, [edx+eax*2]
  442.  
  443. ; X->index = I;
  444.         mov     dword [esi+28], ecx
  445.  
  446. ; X->child[0] = X->child[1] = 0;
  447.         and     dword [esi+20], 0
  448.         and     dword [esi+16], 0
  449.  
  450. ; H = &ms.treebins[I];
  451.  
  452.         mov     eax, ecx
  453.         lea     edx, [mst.treebins+eax*4]
  454.  
  455. ; if (!(ms.treemap & 1<<I))
  456.         bt      [mst.treemap], ecx
  457.         jc      .tree
  458.  
  459. ; ms.treemap |= 1<<I;
  460.         bts     [mst.treemap], ecx
  461. ; *H = X;
  462.         mov     dword [edx], esi
  463.         jmp     .done
  464. .tree:
  465.  
  466. ; T = *H;
  467.         mov     edx, [edx]
  468.  
  469. ; K = S << leftshift_for_tree_index(I);
  470.         mov     eax, ecx
  471.         shr     eax, 1
  472.         sub     ecx, 31
  473.         mov     edi, 37
  474.         sub     edi, eax
  475.         neg     ecx
  476.         sbb     ecx, ecx
  477.         and     ecx, edi
  478.         mov     eax, ebx
  479.         shl     eax, cl    ;eax= K
  480.  
  481.         jmp     .loop
  482. .not_eq_size:
  483.  
  484. ; C = &(T->child[(K >> 31) & 1]);
  485.         mov     ecx, eax
  486.         shr     ecx, 31
  487.         lea     ecx, [edx+ecx*4+16]
  488.  
  489. ; K <<= 1;
  490. ; if (*C != 0)
  491.         mov     edi, [ecx]
  492.         add     eax, eax
  493.         test    edi, edi
  494.         jz      .insert_child
  495.  
  496. ; T = *C;
  497.         mov     edx, edi
  498. .loop:
  499.  
  500. ; for (;;)
  501. ; if ((T->head & ~INUSE_BITS) != S)
  502.  
  503.         mov     ecx, [edx+4]
  504.         and     ecx, not 3
  505.         cmp     ecx, ebx
  506.         jne     .not_eq_size
  507.  
  508. ; F = T->fd;
  509.         mov     eax, [edx+8]
  510.  
  511. ; T->fd = F->bk = X;
  512.         mov     [eax+12], esi
  513.         mov     [edx+8], esi
  514.  
  515. ; X->fd = F;
  516. ; X->bk = T;
  517. ; X->parent = 0;
  518.  
  519.         and     dword [esi+24], 0
  520.         mov     [esi+8], eax
  521.         mov     [esi+12], edx
  522.         ret
  523. .insert_child:
  524.  
  525. ; *C = X;
  526.         mov     [ecx], esi
  527. .done:
  528.  
  529. ; X->parent = T;
  530.         mov     [esi+24], edx
  531.  
  532. ; X->fd = X->bk = X;
  533.         mov     [esi+12], esi
  534.         mov     [esi+8], esi
  535.         ret
  536.  
  537.  
  538. ; param
  539. ;  edx= chunk
  540.  
  541. unlink_large_chunk:
  542.  
  543.         mov     eax, [edx+12]
  544.         cmp     eax, edx
  545.         push    edi
  546.         mov     edi, [edx+24]
  547.         je      @F
  548.  
  549.         mov     ecx, [edx+8]          ;F = X->fd
  550.         mov     [ecx+12], eax         ;F->bk = R;
  551.         mov     [eax+8], ecx          ;R->fd = F
  552.         jmp     .parent
  553. @@:
  554.         mov     eax, [edx+20]
  555.         test    eax, eax
  556.         push    esi
  557.         lea     esi, [edx+20]
  558.         jne     .loop
  559.  
  560.         mov     eax, [edx+16]
  561.         test    eax, eax
  562.         lea     esi, [edx+16]
  563.         je      .l2
  564. .loop:
  565.         cmp     dword [eax+20], 0
  566.         lea     ecx, [eax+20]
  567.         jne     @F
  568.  
  569.         cmp     dword [eax+16], 0
  570.         lea     ecx, [eax+16]
  571.         je      .l1
  572. @@:
  573.         mov     eax, [ecx]
  574.         mov     esi, ecx
  575.         jmp     .loop
  576. .l1:
  577.         mov     dword [esi], 0
  578. .l2:
  579.         pop     esi
  580. .parent:
  581.         test    edi, edi
  582.         je      .done
  583.  
  584.         mov     ecx, [edx+28]
  585.         cmp     edx, [mst.treebins+ecx*4]
  586.         lea     ecx, [mst.treebins+ecx*4]
  587.         jne     .l3
  588.  
  589.         test    eax, eax
  590.         mov     [ecx], eax
  591.         jne     .l5
  592.  
  593.         mov     ecx, [edx+28]
  594.         btr     [mst.treemap], ecx
  595.         pop     edi
  596.         ret
  597.  
  598. .l3:
  599.         cmp     [edi+16], edx
  600.         jne     @F
  601.  
  602.         mov     [edi+16], eax
  603.         jmp     .l4
  604.  
  605. @@:
  606.         mov     [edi+20], eax
  607.  
  608. .l4:
  609.         test    eax, eax
  610.         je      .done
  611.  
  612. .l5:
  613.         mov     [eax+24], edi
  614.         mov     ecx, [edx+16]
  615.         test    ecx, ecx
  616.         je      .l6
  617.  
  618.         mov     [eax+16], ecx
  619.         mov     [ecx+24], eax
  620.  
  621. .l6:
  622.         mov     edx, [edx+20]
  623.         test    edx, edx
  624.         je      .done
  625.  
  626.         mov     [eax+20], edx
  627.         mov     [edx+24], eax
  628.  
  629. .done:
  630.         pop     edi
  631.         ret
  632.  
  633. ; param
  634. ;  esi= nb
  635.  
  636. malloc_small:
  637.         push    ebp
  638.         mov     ebp, esi
  639.  
  640.         push    edi
  641.  
  642.         bsf     eax, [mst.treemap]
  643.         mov     ecx, [mst.treebins+eax*4]
  644.  
  645. ; rsize = (t->head & ~INUSE_BITS) - nb;
  646.  
  647.         mov     edi, [ecx+4]
  648.         and     edi, -4
  649.         sub     edi, esi
  650.  
  651. .loop:
  652.         mov     ebx, ecx
  653.  
  654. .loop_1:
  655.  
  656. ; while ((t = leftmost_child(t)) != 0)
  657.  
  658.         mov     eax, [ecx+16]
  659.         test    eax, eax
  660.         jz      @F
  661.         mov     ecx, eax
  662.         jmp     .l1
  663.  
  664. @@:
  665.         mov     ecx, [ecx+20]
  666.  
  667. .l1:
  668.         test    ecx, ecx
  669.         jz      .unlink
  670.  
  671. ; trem = (t->head & ~INUSE_BITS) - nb;
  672.  
  673.         mov     eax, [ecx+4]
  674.         and     eax, -4
  675.         sub     eax, ebp
  676.  
  677. ; if (trem < rsize)
  678.  
  679.         cmp     eax, edi
  680.         jae     .loop_1
  681.  
  682. ; rsize = trem;
  683.  
  684.         mov     edi, eax
  685.         jmp     .loop
  686. .unlink:
  687.  
  688.  
  689. ; r = chunk_plus_offset((mchunkptr)v, nb);
  690. ; unlink_large_chunk(v);
  691.  
  692.         mov     edx, ebx
  693.         lea     esi, [ebx+ebp]
  694.         call    unlink_large_chunk
  695.  
  696. ; if (rsize < 16)
  697.  
  698.         cmp     edi, 16
  699.         jae     .split
  700.  
  701. ; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  702.  
  703.         lea     ecx, [edi+ebp]
  704.  
  705. ; (v+rsize + nb)->head |= PINUSE_BIT;
  706.  
  707.         add     edi, ebx
  708.         lea     eax, [edi+ebp+4]
  709.         pop     edi
  710.         or      ecx, 3
  711.         mov     [ebx+4], ecx
  712.         or      dword [eax], 1
  713.         pop     ebp
  714.  
  715.         lea     eax, [ebx+8]
  716.         ret
  717.  
  718. .split:
  719.  
  720. ; v->head = nb|PINUSE_BIT|CINUSE_BIT;
  721. ; r->head = rsize|PINUSE_BIT;
  722. ; (r+rsize)->prev_foot = rsize;
  723.  
  724.         or      ebp, 3
  725.         mov     edx, edi
  726.         or      edx, 1
  727.  
  728.         cmp     edi, 256
  729.         mov     [ebx+4], ebp
  730.         mov     [esi+4], edx
  731.         mov     [esi+edi], edi
  732.         jae     .large
  733.  
  734.         shr     edi, 3
  735.         bts     [mst.smallmap], edi
  736.  
  737.         mov     eax, edi
  738.         shl     eax, 4
  739.         add     eax, mst.smallbins
  740.  
  741.         mov     edx, [eax+8]
  742.         mov     [eax+8], esi
  743.         mov     [edx+12], esi
  744.         pop     edi
  745.         mov     [esi+12], eax
  746.         mov     [esi+8], edx
  747.         pop     ebp
  748.         lea     eax, [ebx+8]
  749.         ret
  750.  
  751. .large:
  752.         lea     eax, [ebx+8]
  753.         push    eax
  754.         mov     ebx, edi
  755.         call    insert_large_chunk
  756.         pop     eax
  757.         pop     edi
  758.         pop     ebp
  759.         ret
  760.  
  761.  
  762. ; param
  763. ;  esi= nb
  764.  
  765. malloc_large:
  766. .idx equ esp+4
  767. .rst equ esp
  768.  
  769.         push    ebp
  770.         push    esi
  771.         push    edi
  772.         sub     esp, 8
  773. ; v = 0;
  774. ; rsize = -nb;
  775.  
  776.         mov     edi, esi
  777.         mov     ebx, esi
  778.         xor     ebp, ebp
  779.         neg     edi
  780.  
  781. ; idx = compute_tree_index(nb);
  782.  
  783.         mov     edx, esi
  784.         shr     edx, 8
  785.         bsr     eax, edx
  786.         lea     ecx, [eax+7]
  787.         shr     esi, cl
  788.         and     esi, 1
  789.         lea     ecx, [esi+eax*2]
  790.         mov     [.idx], ecx
  791.  
  792. ; if ((t = ms.treebins[idx]) != 0)
  793.  
  794.         mov     eax, [mst.treebins+ecx*4]
  795.         test    eax, eax
  796.         jz      .l3
  797.  
  798. ; sizebits = nb << leftshift_for_tree_index(idx);
  799.  
  800.         cmp     ecx, 31
  801.         jne     @F
  802.         xor     ecx, ecx
  803.         jmp     .l1
  804.  
  805. @@:
  806.         mov     edx, ecx
  807.         shr     edx, 1
  808.         mov     ecx, 37
  809.         sub     ecx, edx
  810.  
  811. .l1:
  812.         mov     edx, ebx
  813.         shl     edx, cl
  814.  
  815. ; rst = 0;
  816.         mov     [.rst], ebp
  817.  
  818. .loop:
  819.  
  820. ; trem = (t->head & ~INUSE_BITS) - nb;
  821.  
  822.         mov     ecx, [eax+4]
  823.         and     ecx, -4
  824.         sub     ecx, ebx
  825.  
  826. ; if (trem < rsize)
  827.  
  828.         cmp     ecx, edi
  829.         jae     @F
  830. ; v = t;
  831. ; if ((rsize = trem) == 0)
  832.  
  833.         test    ecx, ecx
  834.         mov     ebp, eax
  835.         mov     edi, ecx
  836.         je      .l2
  837.  
  838. @@:
  839.  
  840. ; rt = t->child[1];
  841.  
  842.         mov     ecx, [eax+20]
  843.  
  844. ; t = t->child[(sizebits >> 31) & 1];
  845.  
  846.         mov     esi, edx
  847.         shr     esi, 31
  848.  
  849. ; if (rt != 0 && rt != t)
  850.  
  851.         test    ecx, ecx
  852.         mov     eax, [eax+esi*4+16]
  853.         jz      @F
  854.         cmp     ecx, eax
  855.         jz      @F
  856.  
  857. ; rst = rt;
  858.         mov     [.rst], ecx
  859.  
  860. @@:
  861. ; if (t == 0)
  862.  
  863.         test    eax, eax
  864.         jz      @F
  865.  
  866. ; sizebits <<= 1;
  867.  
  868.         add     edx, edx
  869.         jmp     .loop
  870.  
  871. @@:
  872. ; t = rst;
  873.         mov     eax, [.rst]
  874.  
  875. .l2:
  876. ; if (t == 0 && v == 0)
  877.  
  878.         test    eax, eax
  879.         jne     .l4
  880.         test    ebp, ebp
  881.         jne     .l7
  882.         mov     ecx, [.idx]
  883.  
  884. .l3:
  885.  
  886. ; leftbits = (-1<<idx) & ms.treemap;
  887. ; if (leftbits != 0)
  888.  
  889.         or      edx, -1
  890.         shl     edx, cl
  891.         and     edx, [mst.treemap]
  892.         jz      @F
  893.  
  894.         bsf     eax, edx
  895. ; t = ms.treebins[i];
  896.         mov     eax, [mst.treebins+eax*4]
  897.  
  898. @@:
  899.  
  900. ; while (t != 0)
  901.         test    eax, eax
  902.         jz      .l5
  903.  
  904. .l4:
  905.  
  906. ; trem = (t->head & ~INUSE_BITS) - nb;
  907.  
  908.         mov     ecx, [eax+4]
  909.         and     ecx, -4
  910.         sub     ecx, ebx
  911.  
  912. ; if (trem < rsize)
  913.  
  914.         cmp     ecx, edi
  915.         jae     @F
  916. ; rsize = trem;
  917.  
  918.         mov     edi, ecx
  919. ; v = t;
  920.         mov     ebp, eax
  921.  
  922. @@:
  923.  
  924. ; t = leftmost_child(t);
  925.  
  926.         mov     ecx, [eax+16]
  927.         test    ecx, ecx
  928.         je      @F
  929.         mov     eax, ecx
  930.         jmp     .l6
  931.  
  932. @@:
  933.         mov     eax, [eax+20]
  934.  
  935. .l6:
  936.  
  937. ; while (t != 0)
  938.  
  939.         test    eax, eax
  940.         jne     .l4
  941.  
  942. .l5:
  943.  
  944. ; if (v != 0)
  945.  
  946.         test    ebp, ebp
  947.         jz      .done
  948.  
  949. .l7:
  950.  
  951. ; r = chunk_plus_offset((mchunkptr)v, nb);
  952. ; unlink_large_chunk(v);
  953.  
  954.         mov     edx, ebp
  955.         lea     esi, [ebx+ebp]
  956.         call    unlink_large_chunk
  957.  
  958. ; if (rsize < 16)
  959.  
  960.         cmp     edi, 16
  961.         jae     .large
  962.  
  963. ; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  964.  
  965.         lea     ecx, [edi+ebx]
  966.  
  967. ; (v+rsize + nb)->head |= PINUSE_BIT;
  968.  
  969.         add     edi, ebp
  970.         lea     eax, [edi+ebx+4]
  971.         or      ecx, 3
  972.         mov     [ebp+4], ecx
  973.         or      dword [eax], 1
  974.         lea     eax, [ebp+8]
  975.         add     esp, 8
  976.         pop     edi
  977.         pop     esi
  978.         pop     ebp
  979.         ret
  980.  
  981. .large:
  982.  
  983. ; v->head = nb|PINUSE_BIT|CINUSE_BIT;
  984. ; r->head = rsize|PINUSE_BIT;
  985.  
  986.         mov     edx, edi
  987.         or      ebx, 3
  988.         mov     [ebp+4], ebx
  989.         or      edx, 1
  990.         mov     [esi+4], edx
  991.  
  992. ; (r+rsize)->prev_foot = rsize;
  993. ; insert_large_chunk((tchunkptr)r, rsize);
  994.  
  995.         mov     [esi+edi], edi
  996.         mov     eax, edi
  997.         mov     ecx, esi
  998.         call    insert_chunk
  999.  
  1000.         lea     eax, [ebp+8]
  1001.         add     esp, 8
  1002.         pop     edi
  1003.         pop     esi
  1004.         pop     ebp
  1005.         ret
  1006.  
  1007. .done:
  1008.         add     esp, 8
  1009.         pop     edi
  1010.         pop     esi
  1011.         pop     ebp
  1012.         xor     eax, eax
  1013.         ret
  1014.  
  1015. init_malloc:
  1016.  
  1017.         stdcall kernel_alloc, 0x40000
  1018.  
  1019.         mov     [mst.top], eax
  1020.         mov     [mst.topsize], 128*1024
  1021.         mov     dword [eax+4], (128*1024) or 1
  1022.         mov     eax, mst.smallbins
  1023.  
  1024. @@:
  1025.         mov     [eax+8], eax
  1026.         mov     [eax+12], eax
  1027.         add     eax, 16
  1028.         cmp     eax, mst.smallbins+512
  1029.         jb      @B
  1030.  
  1031.         mov     ecx, mst.mutex
  1032.         call    mutex_init
  1033.  
  1034.         ret
  1035.  
  1036.