Subversion Repositories Kolibri OS

Rev

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

  1. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  2. ;;                                                              ;;
  3. ;; Copyright (C) KolibriOS team 2004-2011. All rights reserved. ;;
  4. ;; Distributed under terms of the GNU General Public License    ;;
  5. ;;                                                              ;;
  6. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  7.  
  8. $Revision: 2455 $
  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    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
  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    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
  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.         pop     esi
  345.         mov     ecx, edi
  346.         pop     edi
  347.         jmp     insert_chunk
  348. .unl_large:
  349.  
  350. ; unlink_large_chunk((tchunkptr)next);
  351.  
  352.         mov     edx, ebx
  353.         call    unlink_large_chunk
  354. ; p->head = psize|PINUSE_BIT;
  355.  
  356.         mov     ecx, esi
  357.         or      ecx, 1
  358.         mov     [edi+4], ecx
  359.  
  360. ; (p+psize)->prev_foot = psize;
  361.  
  362.         mov     [esi+edi], esi
  363.  
  364. ; insert_chunk(p,psize);
  365.  
  366.         mov     eax, esi
  367.         pop     esi
  368.         mov     ecx, edi
  369.         pop     edi
  370.         jmp     insert_chunk
  371. .fix_next:
  372.  
  373. ; (p+psize)->prev_foot = psize;
  374. ; next->head &= ~PINUSE_BIT;
  375. ; p->head = psize|PINUSE_BIT;
  376.  
  377.         and     eax, -2
  378.         mov     edx, esi
  379.         mov     [ebx+4], eax
  380.         or      edx, 1
  381.         mov     [edi+4], edx
  382.  
  383. ; (p+psize)->prev_foot = psize;
  384.  
  385.         mov     [esi+edi], esi
  386. ; insert_chunk(p,psize);
  387.  
  388.         mov     eax, esi
  389.         pop     esi
  390.         mov     ecx, edi
  391.         pop     edi
  392.         jmp     insert_chunk
  393.  
  394. ; param
  395. ;  ecx = chunk
  396. ;  eax = size
  397.  
  398. insert_chunk:
  399.  
  400.         cmp     eax, 256
  401.         push    esi
  402.         mov     esi, ecx
  403.         jae     .large
  404.  
  405. ; I  = S>>3;
  406. ; ms.smallmap |=  1<< I;
  407.  
  408.         shr     eax, 3
  409.         bts     [mst.smallmap], eax
  410.  
  411. ; B = &ms.smallbins[I];
  412.  
  413.         shl     eax, 4
  414.         add     eax, mst.smallbins
  415.         mov     edx, [eax+8]           ;F = B->fd
  416.         mov     [eax+8], esi           ;B->fd = P
  417.         mov     [edx+12], esi          ;F->bk = P
  418.         mov     [esi+8], edx           ;P->fd = F
  419.         mov     [esi+12], eax          ;P->bk = B
  420.         pop     esi
  421.         mov     ecx, mst.mutex
  422.         call    mutex_unlock
  423.         ret
  424. .large:
  425.         mov     ebx, eax
  426.         call    insert_large_chunk
  427.         pop     esi
  428.         mov     ecx, mst.mutex
  429.         call    mutex_unlock
  430.         ret
  431.  
  432.  
  433. ; param
  434. ;  esi= chunk
  435. ;  ebx= size
  436.  
  437. insert_large_chunk:
  438.  
  439. ; I = compute_tree_index(S);
  440.  
  441.         mov     edx, ebx
  442.         shr     edx, 8
  443.         bsr     eax, edx
  444.         lea     ecx, [eax+7]
  445.         mov     edx, ebx
  446.         shr     edx, cl
  447.         and     edx, 1
  448.         lea     ecx, [edx+eax*2]
  449.  
  450. ; X->index = I;
  451.         mov     dword [esi+28], ecx
  452.  
  453. ; X->child[0] = X->child[1] = 0;
  454.         and     dword [esi+20], 0
  455.         and     dword [esi+16], 0
  456.  
  457. ; H = &ms.treebins[I];
  458.  
  459.         mov     eax, ecx
  460.         lea     edx, [mst.treebins+eax*4]
  461.  
  462. ; if (!(ms.treemap & 1<<I))
  463.         bt      [mst.treemap], ecx
  464.         jc      .tree
  465.  
  466. ; ms.treemap |= 1<<I;
  467.         bts     [mst.treemap], ecx
  468. ; *H = X;
  469.         mov     dword [edx], esi
  470.         jmp     .done
  471. .tree:
  472.  
  473. ; T = *H;
  474.         mov     edx, [edx]
  475.  
  476. ; K = S << leftshift_for_tree_index(I);
  477.         mov     eax, ecx
  478.         shr     eax, 1
  479.         sub     ecx, 31
  480.         mov     edi, 37
  481.         sub     edi, eax
  482.         neg     ecx
  483.         sbb     ecx, ecx
  484.         and     ecx, edi
  485.         mov     eax, ebx
  486.         shl     eax, cl    ;eax= K
  487.  
  488.         jmp     .loop
  489. .not_eq_size:
  490.  
  491. ; C = &(T->child[(K >> 31) & 1]);
  492.         mov     ecx, eax
  493.         shr     ecx, 31
  494.         lea     ecx, [edx+ecx*4+16]
  495.  
  496. ; K <<= 1;
  497. ; if (*C != 0)
  498.         mov     edi, [ecx]
  499.         add     eax, eax
  500.         test    edi, edi
  501.         jz      .insert_child
  502.  
  503. ; T = *C;
  504.         mov     edx, edi
  505. .loop:
  506.  
  507. ; for (;;)
  508. ; if ((T->head & ~INUSE_BITS) != S)
  509.  
  510.         mov     ecx, [edx+4]
  511.         and     ecx, not 3
  512.         cmp     ecx, ebx
  513.         jne     .not_eq_size
  514.  
  515. ; F = T->fd;
  516.         mov     eax, [edx+8]
  517.  
  518. ; T->fd = F->bk = X;
  519.         mov     [eax+12], esi
  520.         mov     [edx+8], esi
  521.  
  522. ; X->fd = F;
  523. ; X->bk = T;
  524. ; X->parent = 0;
  525.  
  526.         and     dword [esi+24], 0
  527.         mov     [esi+8], eax
  528.         mov     [esi+12], edx
  529.         ret
  530. .insert_child:
  531.  
  532. ; *C = X;
  533.         mov     [ecx], esi
  534. .done:
  535.  
  536. ; X->parent = T;
  537.         mov     [esi+24], edx
  538.  
  539. ; X->fd = X->bk = X;
  540.         mov     [esi+12], esi
  541.         mov     [esi+8], esi
  542.         ret
  543.  
  544.  
  545. ; param
  546. ;  edx= chunk
  547.  
  548. unlink_large_chunk:
  549.  
  550.         mov     eax, [edx+12]
  551.         cmp     eax, edx
  552.         push    edi
  553.         mov     edi, [edx+24]
  554.         je      @F
  555.  
  556.         mov     ecx, [edx+8]          ;F = X->fd
  557.         mov     [ecx+12], eax         ;F->bk = R;
  558.         mov     [eax+8], ecx          ;R->fd = F
  559.         jmp     .parent
  560. @@:
  561.         mov     eax, [edx+20]
  562.         test    eax, eax
  563.         push    esi
  564.         lea     esi, [edx+20]
  565.         jne     .loop
  566.  
  567.         mov     eax, [edx+16]
  568.         test    eax, eax
  569.         lea     esi, [edx+16]
  570.         je      .l2
  571. .loop:
  572.         cmp     dword [eax+20], 0
  573.         lea     ecx, [eax+20]
  574.         jne     @F
  575.  
  576.         cmp     dword [eax+16], 0
  577.         lea     ecx, [eax+16]
  578.         je      .l1
  579. @@:
  580.         mov     eax, [ecx]
  581.         mov     esi, ecx
  582.         jmp     .loop
  583. .l1:
  584.         mov     dword [esi], 0
  585. .l2:
  586.         pop     esi
  587. .parent:
  588.         test    edi, edi
  589.         je      .done
  590.  
  591.         mov     ecx, [edx+28]
  592.         cmp     edx, [mst.treebins+ecx*4]
  593.         lea     ecx, [mst.treebins+ecx*4]
  594.         jne     .l3
  595.  
  596.         test    eax, eax
  597.         mov     [ecx], eax
  598.         jne     .l5
  599.  
  600.         mov     ecx, [edx+28]
  601.         btr     [mst.treemap], ecx
  602.         pop     edi
  603.         ret
  604.  
  605. .l3:
  606.         cmp     [edi+16], edx
  607.         jne     @F
  608.  
  609.         mov     [edi+16], eax
  610.         jmp     .l4
  611.  
  612. @@:
  613.         mov     [edi+20], eax
  614.  
  615. .l4:
  616.         test    eax, eax
  617.         je      .done
  618.  
  619. .l5:
  620.         mov     [eax+24], edi
  621.         mov     ecx, [edx+16]
  622.         test    ecx, ecx
  623.         je      .l6
  624.  
  625.         mov     [eax+16], ecx
  626.         mov     [ecx+24], eax
  627.  
  628. .l6:
  629.         mov     edx, [edx+20]
  630.         test    edx, edx
  631.         je      .done
  632.  
  633.         mov     [eax+20], edx
  634.         mov     [edx+24], eax
  635.  
  636. .done:
  637.         pop     edi
  638.         ret
  639.  
  640. ; param
  641. ;  esi= nb
  642.  
  643. malloc_small:
  644.         push    ebp
  645.         mov     ebp, esi
  646.  
  647.         push    edi
  648.  
  649.         bsf     eax, [mst.treemap]
  650.         mov     ecx, [mst.treebins+eax*4]
  651.  
  652. ; rsize = (t->head & ~INUSE_BITS) - nb;
  653.  
  654.         mov     edi, [ecx+4]
  655.         and     edi, -4
  656.         sub     edi, esi
  657.  
  658. .loop:
  659.         mov     ebx, ecx
  660.  
  661. .loop_1:
  662.  
  663. ; while ((t = leftmost_child(t)) != 0)
  664.  
  665.         mov     eax, [ecx+16]
  666.         test    eax, eax
  667.         jz      @F
  668.         mov     ecx, eax
  669.         jmp     .l1
  670.  
  671. @@:
  672.         mov     ecx, [ecx+20]
  673.  
  674. .l1:
  675.         test    ecx, ecx
  676.         jz      .unlink
  677.  
  678. ; trem = (t->head & ~INUSE_BITS) - nb;
  679.  
  680.         mov     eax, [ecx+4]
  681.         and     eax, -4
  682.         sub     eax, ebp
  683.  
  684. ; if (trem < rsize)
  685.  
  686.         cmp     eax, edi
  687.         jae     .loop_1
  688.  
  689. ; rsize = trem;
  690.  
  691.         mov     edi, eax
  692.         jmp     .loop
  693. .unlink:
  694.  
  695.  
  696. ; r = chunk_plus_offset((mchunkptr)v, nb);
  697. ; unlink_large_chunk(v);
  698.  
  699.         mov     edx, ebx
  700.         lea     esi, [ebx+ebp]
  701.         call    unlink_large_chunk
  702.  
  703. ; if (rsize < 16)
  704.  
  705.         cmp     edi, 16
  706.         jae     .split
  707.  
  708. ; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  709.  
  710.         lea     ecx, [edi+ebp]
  711.  
  712. ; (v+rsize + nb)->head |= PINUSE_BIT;
  713.  
  714.         add     edi, ebx
  715.         lea     eax, [edi+ebp+4]
  716.         pop     edi
  717.         or      ecx, 3
  718.         mov     [ebx+4], ecx
  719.         or      dword [eax], 1
  720.         pop     ebp
  721.  
  722.         lea     eax, [ebx+8]
  723.         ret
  724.  
  725. .split:
  726.  
  727. ; v->head = nb|PINUSE_BIT|CINUSE_BIT;
  728. ; r->head = rsize|PINUSE_BIT;
  729. ; (r+rsize)->prev_foot = rsize;
  730.  
  731.         or      ebp, 3
  732.         mov     edx, edi
  733.         or      edx, 1
  734.  
  735.         cmp     edi, 256
  736.         mov     [ebx+4], ebp
  737.         mov     [esi+4], edx
  738.         mov     [esi+edi], edi
  739.         jae     .large
  740.  
  741.         shr     edi, 3
  742.         bts     [mst.smallmap], edi
  743.  
  744.         mov     eax, edi
  745.         shl     eax, 4
  746.         add     eax, mst.smallbins
  747.  
  748.         mov     edx, [eax+8]
  749.         mov     [eax+8], esi
  750.         mov     [edx+12], esi
  751.         pop     edi
  752.         mov     [esi+12], eax
  753.         mov     [esi+8], edx
  754.         pop     ebp
  755.         lea     eax, [ebx+8]
  756.         ret
  757.  
  758. .large:
  759.         lea     eax, [ebx+8]
  760.         push    eax
  761.         mov     ebx, edi
  762.         call    insert_large_chunk
  763.         pop     eax
  764.         pop     edi
  765.         pop     ebp
  766.         ret
  767.  
  768.  
  769. ; param
  770. ;  esi= nb
  771.  
  772. malloc_large:
  773. .idx equ esp+4
  774. .rst equ esp
  775.  
  776.         push    ebp
  777.         push    esi
  778.         push    edi
  779.         sub     esp, 8
  780. ; v = 0;
  781. ; rsize = -nb;
  782.  
  783.         mov     edi, esi
  784.         mov     ebx, esi
  785.         xor     ebp, ebp
  786.         neg     edi
  787.  
  788. ; idx = compute_tree_index(nb);
  789.  
  790.         mov     edx, esi
  791.         shr     edx, 8
  792.         bsr     eax, edx
  793.         lea     ecx, [eax+7]
  794.         shr     esi, cl
  795.         and     esi, 1
  796.         lea     ecx, [esi+eax*2]
  797.         mov     [.idx], ecx
  798.  
  799. ; if ((t = ms.treebins[idx]) != 0)
  800.  
  801.         mov     eax, [mst.treebins+ecx*4]
  802.         test    eax, eax
  803.         jz      .l3
  804.  
  805. ; sizebits = nb << leftshift_for_tree_index(idx);
  806.  
  807.         cmp     ecx, 31
  808.         jne     @F
  809.         xor     ecx, ecx
  810.         jmp     .l1
  811.  
  812. @@:
  813.         mov     edx, ecx
  814.         shr     edx, 1
  815.         mov     ecx, 37
  816.         sub     ecx, edx
  817.  
  818. .l1:
  819.         mov     edx, ebx
  820.         shl     edx, cl
  821.  
  822. ; rst = 0;
  823.         mov     [.rst], ebp
  824.  
  825. .loop:
  826.  
  827. ; trem = (t->head & ~INUSE_BITS) - nb;
  828.  
  829.         mov     ecx, [eax+4]
  830.         and     ecx, -4
  831.         sub     ecx, ebx
  832.  
  833. ; if (trem < rsize)
  834.  
  835.         cmp     ecx, edi
  836.         jae     @F
  837. ; v = t;
  838. ; if ((rsize = trem) == 0)
  839.  
  840.         test    ecx, ecx
  841.         mov     ebp, eax
  842.         mov     edi, ecx
  843.         je      .l2
  844.  
  845. @@:
  846.  
  847. ; rt = t->child[1];
  848.  
  849.         mov     ecx, [eax+20]
  850.  
  851. ; t = t->child[(sizebits >> 31) & 1];
  852.  
  853.         mov     esi, edx
  854.         shr     esi, 31
  855.  
  856. ; if (rt != 0 && rt != t)
  857.  
  858.         test    ecx, ecx
  859.         mov     eax, [eax+esi*4+16]
  860.         jz      @F
  861.         cmp     ecx, eax
  862.         jz      @F
  863.  
  864. ; rst = rt;
  865.         mov     [.rst], ecx
  866.  
  867. @@:
  868. ; if (t == 0)
  869.  
  870.         test    eax, eax
  871.         jz      @F
  872.  
  873. ; sizebits <<= 1;
  874.  
  875.         add     edx, edx
  876.         jmp     .loop
  877.  
  878. @@:
  879. ; t = rst;
  880.         mov     eax, [.rst]
  881.  
  882. .l2:
  883. ; if (t == 0 && v == 0)
  884.  
  885.         test    eax, eax
  886.         jne     .l4
  887.         test    ebp, ebp
  888.         jne     .l7
  889.         mov     ecx, [.idx]
  890.  
  891. .l3:
  892.  
  893. ; leftbits = (-1<<idx) & ms.treemap;
  894. ; if (leftbits != 0)
  895.  
  896.         or      edx, -1
  897.         shl     edx, cl
  898.         and     edx, [mst.treemap]
  899.         jz      @F
  900.  
  901.         bsf     eax, edx
  902. ; t = ms.treebins[i];
  903.         mov     eax, [mst.treebins+eax*4]
  904.  
  905. @@:
  906.  
  907. ; while (t != 0)
  908.         test    eax, eax
  909.         jz      .l5
  910.  
  911. .l4:
  912.  
  913. ; trem = (t->head & ~INUSE_BITS) - nb;
  914.  
  915.         mov     ecx, [eax+4]
  916.         and     ecx, -4
  917.         sub     ecx, ebx
  918.  
  919. ; if (trem < rsize)
  920.  
  921.         cmp     ecx, edi
  922.         jae     @F
  923. ; rsize = trem;
  924.  
  925.         mov     edi, ecx
  926. ; v = t;
  927.         mov     ebp, eax
  928.  
  929. @@:
  930.  
  931. ; t = leftmost_child(t);
  932.  
  933.         mov     ecx, [eax+16]
  934.         test    ecx, ecx
  935.         je      @F
  936.         mov     eax, ecx
  937.         jmp     .l6
  938.  
  939. @@:
  940.         mov     eax, [eax+20]
  941.  
  942. .l6:
  943.  
  944. ; while (t != 0)
  945.  
  946.         test    eax, eax
  947.         jne     .l4
  948.  
  949. .l5:
  950.  
  951. ; if (v != 0)
  952.  
  953.         test    ebp, ebp
  954.         jz      .done
  955.  
  956. .l7:
  957.  
  958. ; r = chunk_plus_offset((mchunkptr)v, nb);
  959. ; unlink_large_chunk(v);
  960.  
  961.         mov     edx, ebp
  962.         lea     esi, [ebx+ebp]
  963.         call    unlink_large_chunk
  964.  
  965. ; if (rsize < 16)
  966.  
  967.         cmp     edi, 16
  968.         jae     .large
  969.  
  970. ; v->head = (rsize + nb)|PINUSE_BIT|CINUSE_BIT;
  971.  
  972.         lea     ecx, [edi+ebx]
  973.  
  974. ; (v+rsize + nb)->head |= PINUSE_BIT;
  975.  
  976.         add     edi, ebp
  977.         lea     eax, [edi+ebx+4]
  978.         or      ecx, 3
  979.         mov     [ebp+4], ecx
  980.         or      dword [eax], 1
  981.         lea     eax, [ebp+8]
  982.         add     esp, 8
  983.         pop     edi
  984.         pop     esi
  985.         pop     ebp
  986.         ret
  987.  
  988. .large:
  989.  
  990. ; v->head = nb|PINUSE_BIT|CINUSE_BIT;
  991. ; r->head = rsize|PINUSE_BIT;
  992.  
  993.         mov     edx, edi
  994.         or      ebx, 3
  995.         mov     [ebp+4], ebx
  996.         or      edx, 1
  997.         mov     [esi+4], edx
  998.  
  999. ; (r+rsize)->prev_foot = rsize;
  1000. ; insert_large_chunk((tchunkptr)r, rsize);
  1001.  
  1002.         mov     [esi+edi], edi
  1003.         mov     eax, edi
  1004.         mov     ecx, esi
  1005.         call    insert_chunk
  1006.  
  1007.         lea     eax, [ebp+8]
  1008.         add     esp, 8
  1009.         pop     edi
  1010.         pop     esi
  1011.         pop     ebp
  1012.         ret
  1013.  
  1014. .done:
  1015.         add     esp, 8
  1016.         pop     edi
  1017.         pop     esi
  1018.         pop     ebp
  1019.         xor     eax, eax
  1020.         ret
  1021.  
  1022. init_malloc:
  1023.  
  1024.         stdcall kernel_alloc, 0x40000
  1025.  
  1026.         mov     [mst.top], eax
  1027.         mov     [mst.topsize], 128*1024
  1028.         mov     dword [eax+4], (128*1024) or 1
  1029.         mov     eax, mst.smallbins
  1030.  
  1031. @@:
  1032.         mov     [eax+8], eax
  1033.         mov     [eax+12], eax
  1034.         add     eax, 16
  1035.         cmp     eax, mst.smallbins+512
  1036.         jb      @B
  1037.  
  1038.         mov     ecx, mst.mutex
  1039.         call    mutex_init
  1040.  
  1041.         ret
  1042.  
  1043.