Subversion Repositories Kolibri OS

Rev

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

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