workbench/hidds/radeon/bitmap.c

   1 /*
   2     Copyright � 2003-2007, The AROS Development Team. All rights reserved.
   3     $Id$
   4 */
   5
   6 #define DEBUG 0
   7 #include "bitmap.h"
   8 #include <exec/types.h>
   9 #include <proto/exec.h>
  10 #include <aros/debug.h>
  11 #include <exec/memory.h>
  12 #include <exec/memheaderext.h>
  13
  14 LONG bfffo(ULONG val, UBYTE bitoffset)
  15 {
  16     val &= (0xffffffff >> bitoffset);
  17     if (val)
  18         return __builtin_clz(val);
  19     else
  20         return 32;
  21 }
  22
  23 LONG bfflo(ULONG val, UBYTE bitoffset)
  24 {
  25     val &= (0xffffffff << (31-bitoffset));
  26     if (val)
  27         return 31-__builtin_ctz(val);
  28     else
  29         return -1;
  30 }
  31
  32 LONG bfffz(ULONG val, UBYTE bitoffset)
  33 {
  34     return bfffo(~val, bitoffset);
  35 }
  36
  37 LONG bfflz(ULONG val, UBYTE bitoffset)
  38 {
  39     return bfflo(~val, bitoffset);
  40 }
  41
  42 ULONG bfset(ULONG data, UBYTE bitoffset, UBYTE bits)
  43 {
  44     ULONG mask = ~((1 << (32 - bits)) - 1);
  45     mask >>= bitoffset;
  46     return data | mask;
  47 }
  48
  49 ULONG bfclr(ULONG data, UBYTE bitoffset, UBYTE bits)
  50 {
  51     ULONG mask = ~((1 << (32 - bits)) - 1);
  52     mask >>= bitoffset;
  53     return data & ~mask;
  54 }
  55
  56 ULONG bfcnto(ULONG v)
  57 {
  58     ULONG const w = v - ((v >> 1) & 0x55555555);                    // temp
  59     ULONG const x = (w & 0x33333333) + ((w >> 2) & 0x33333333);     // temp
  60     ULONG const c = ((x + ((x >> 4) & 0xF0F0F0F)) * 0x1010101) >> 24; // count
  61
  62     return c;
  63 }
  64
  65 ULONG bfcntz(ULONG v)
  66 {
  67     return bfcnto(~v);
  68 }
  69
  70 LONG bmffo(ULONG *bitmap, ULONG longs, LONG bitoffset)
  71 {
  72     ULONG *scan = bitmap;
  73     ULONG err = 32*longs;
  74     int longoffset, bit;
  75
  76     longoffset = bitoffset >> 5;
  77     longs -= longoffset;
  78     scan += longoffset;
  79
  80     bitoffset = bitoffset & 0x1F;
  81
  82     if (bitoffset != 0) {
  83         if ((bit = bfffo(*scan, bitoffset)) < 32) {
  84             return (bit + ((scan - bitmap) << 5));
  85         }
  86         scan++;
  87         longs--;
  88     }
  89
  90     while (longs-- > 0) {
  91         if (*scan++ != 0) {
  92             scan--;
  93             return (bfffo(*scan,0) + ((scan - bitmap) << 5));
  94         }
  95     }
  96
  97     return (err);
  98 }
  99
 100 LONG bmffz(ULONG *bitmap, ULONG longs, LONG bitoffset)
 101 {
 102     ULONG *scan = bitmap;
 103     ULONG err = 32*longs;
 104     int longoffset, bit;
 105
 106     longoffset = bitoffset >> 5;
 107     longs -= longoffset;
 108     scan += longoffset;
 109
 110     bitoffset = bitoffset & 0x1F;
 111
 112     if (bitoffset != 0) {
 113         if ((bit = bfffz(*scan, bitoffset)) < 32) {
 114             return (bit + ((scan - bitmap) << 5));
 115         }
 116         scan++;
 117         longs--;
 118     }
 119
 120     while (longs-- > 0) {
 121         if (*scan++ != 0xFFFFFFFF) {
 122             scan--;
 123             return (bfffz(*scan,0) + ((scan - bitmap) << 5));
 124         }
 125     }
 126
 127     return (err);
 128 }
 129
 130 LONG bmclr(ULONG *bitmap, ULONG longs, LONG bitoffset, LONG bits)
 131 {
 132     ULONG *scan = bitmap;
 133     int longoffset;
 134     int orgbits = bits;
 135
 136     longoffset = bitoffset >> 5;
 137     longs -= longoffset;
 138     scan += longoffset;
 139
 140     bitoffset = bitoffset & 0x1F;
 141
 142     if (bitoffset != 0) {
 143         if (bits < 32) {
 144             *scan = bfclr(*scan, bitoffset, bits);
 145         } else {
 146             *scan = bfclr(*scan, bitoffset, 32);
 147         }
 148         scan++;
 149         longs--;
 150         bits -= 32 - bitoffset;
 151     }
 152
 153     while (bits > 0 && longs-- > 0) {
 154         if (bits > 31) {
 155             *scan++ = 0;
 156         } else {
 157             *scan = bfclr(*scan, 0, bits);
 158         }
 159         bits -= 32;
 160     }
 161
 162     if (bits <= 0) {
 163         return (orgbits);
 164     }
 165     return (orgbits - bits);
 166 }
 167
 168 LONG bmset(ULONG *bitmap, ULONG longs, LONG bitoffset, LONG bits)
 169 {
 170     ULONG *scan = bitmap;
 171     int longoffset;
 172     int orgbits = bits;
 173
 174     longoffset = bitoffset >> 5;
 175     longs -= longoffset;
 176     scan += longoffset;
 177
 178     bitoffset = bitoffset & 0x1F;
 179
 180     if (bitoffset != 0) {
 181         if (bits < 32) {
 182             *scan = (bfset((*scan), bitoffset, bits));
 183         } else {
 184             *scan = (bfset((*scan), bitoffset, 32));
 185         }
 186         scan++;
 187         longs--;
 188         bits -= 32 - bitoffset;
 189     }
 190
 191     while (bits > 0 && longs-- > 0) {
 192         if (bits > 31) {
 193             *scan++ = 0xFFFFFFFF;
 194         } else {
 195             *scan = (bfset((*scan), 0, bits));
 196         }
 197         bits -= 32;
 198     }
 199
 200     if (bits <= 0) {
 201         return (orgbits);
 202     }
 203     return (orgbits - bits);
 204 }
 205
 206 int bmtstz(ULONG *bitmap, ULONG bitoffset, LONG bits)
 207 {
 208     LONG longoffset = bitoffset >> 5;
 209     ULONG *scan = bitmap;
 210     ULONG mask;
 211
 212     scan += longoffset;
 213     bitoffset &= 0x1f;
 214
 215     if (bitoffset != 0)
 216     {
 217         if ((bits + bitoffset) < 32)
 218         {
 219             mask = (0xffffffff >> bitoffset) & (0xffffffff << (32 - (bits+bitoffset)));
 220             bits=0;
 221         }
 222         else
 223         {
 224             mask = (0xffffffff >> bitoffset);
 225             bits -= (32-bitoffset);
 226         }
 227         if ((mask & (*scan++)) != 0)
 228             return 0;
 229     }
 230
 231     while (bits > 0)
 232     {
 233         if (bits >= 32)
 234         {
 235             mask=0xffffffff;
 236             bits -= 32;
 237         }
 238         else
 239         {
 240             mask = 0xffffffff << (32-bits);
 241             bits = 0;
 242         }
 243         if ((mask & (*scan++)) != 0)
 244             return 0;
 245     }
 246
 247     return 1;
 248 }
 249
 250 ULONG bmcnto(ULONG *bitmap, LONG bitoffset, LONG bits)
 251 {
 252     LONG longoffset = bitoffset >> 5;
 253     ULONG *scan = bitmap;
 254     ULONG count = 0;
 255     ULONG mask;
 256
 257     scan += longoffset;
 258     bitoffset &= 0x1f;
 259
 260     if (bitoffset != 0)
 261     {
 262         if ((bits + bitoffset) < 32)
 263         {
 264             mask = (0xffffffff >> bitoffset) & (0xffffffff << (32 - (bits+bitoffset)));
 265             bits=0;
 266         }
 267         else
 268         {
 269             mask = (0xffffffff >> bitoffset);
 270             bits -= (32-bitoffset);
 271         }
 272         count += bfcnto(*scan++ & mask);
 273     }
 274
 275     while (bits > 0)
 276     {
 277         if (bits >= 32)
 278         {
 279             mask=0xffffffff;
 280             bits -= 32;
 281         }
 282         else
 283         {
 284             mask = 0xffffffff << (32-bits);
 285             bits = 0;
 286         }
 287         count += bfcnto(*scan++ & mask);
 288     }
 289
 290     return count;
 291 }
 292
 293 ULONG bmcntz(ULONG *bitmap, LONG bitoffset, LONG bits)
 294 {
 295     LONG longoffset = bitoffset >> 5;
 296     ULONG *scan = bitmap;
 297     ULONG count = 0;
 298     ULONG mask;
 299
 300     scan += longoffset;
 301     bitoffset &= 0x1f;
 302
 303     if (bitoffset != 0)
 304     {
 305         if ((bits + bitoffset) < 32)
 306         {
 307             mask = ~((0xffffffff >> bitoffset) & (0xffffffff << (32 - (bits+bitoffset))));
 308             bits=0;
 309         }
 310         else
 311         {
 312             mask = ~(0xffffffff >> bitoffset);
 313             bits -= (32-bitoffset);
 314         }
 315
 316         count += bfcntz(*scan++ | mask);
 317     }
 318
 319     while (bits > 0)
 320     {
 321         if (bits >= 32)
 322         {
 323             mask=0;
 324             bits -= 32;
 325         }
 326         else
 327         {
 328             mask = ~(0xffffffff << (32-bits));
 329             bits = 0;
 330         }
 331
 332         count += bfcntz(*scan++ | mask);
 333     }
 334
 335     return count;
 336 }
 337
 338 void *mh_Alloc(struct MemHeaderExt *mhe, IPTR size, ULONG *flags)
 339 {
 340         return NULL;
 341 }
 342
 343 void mh_Free(struct MemHeaderExt *mhe, APTR  mem,  IPTR size)
 344 {
 345 }
 346
 347 void *mh_AllocAbs(struct MemHeaderExt *mhe, IPTR size, APTR  mem)
 348 {
 349         return NULL;
 350 }
 351
 352 void *mh_ReAlloc(struct MemHeaderExt *mhe, APTR  old,  IPTR size)
 353 {
 354         return NULL;
 355 }
 356
 357 IPTR mh_Avail(struct MemHeaderExt *mhe, ULONG flags)
 358 {
 359         struct ati_staticdata *sd = (APTR)mhe->mhe_UserData;
 360         IPTR size = 0;
 361
 362 //      Forbid();
 363
 364         ObtainSemaphore(&sd->CardMemLock);
 365
 366         if (flags & MEMF_TOTAL)
 367                 size = sd->Card.FbUsableSize;
 368         else if (flags & MEMF_LARGEST)
 369         {
 370                 ULONG ptr;
 371
 372                 ptr = bmffz(sd->CardMemBmp, sd->CardMemSize, 0);
 373
 374             while (ptr < (sd->CardMemSize << 5))
 375             {
 376                 ULONG tmpptr = bmffo(sd->CardMemBmp, sd->CardMemSize, ptr);
 377
 378                 if ((tmpptr - ptr) > size)
 379                         size = tmpptr - ptr;
 380
 381                 ptr = bmffz(sd->CardMemBmp, sd->CardMemSize, tmpptr);
 382             }
 383
 384             size <<= 10;
 385         }
 386         else
 387                 size = bmcntz(sd->CardMemBmp, 0, sd->Card.FbUsableSize >> 10) << 10;
 388
 389 //    Permit();
 390
 391         ReleaseSemaphore(&sd->CardMemLock);
 392
 393         return size;
 394 }
 395
 396 void BitmapInit(struct ati_staticdata *sd)
 397 {
 398     /*
 399      * If Radeon chip has some video memory, create a bitmap representing all allocations.
 400      * Divide whole memory into 1KB chunks
 401      */
 402     if (sd->Card.FbUsableSize)
 403     {
 404         sd->CardMemBmp = AllocPooled(sd->memPool, sd->Card.FbUsableSize >> 13);
 405
 406         sd->managedMem.mhe_MemHeader.mh_Node.ln_Type = NT_MEMORY;
 407         sd->managedMem.mhe_MemHeader.mh_Node.ln_Name = "Radeon VRAM";
 408         sd->managedMem.mhe_MemHeader.mh_Node.ln_Pri = -128;
 409         sd->managedMem.mhe_MemHeader.mh_Attributes = MEMF_CHIP | MEMF_MANAGED | MEMF_PUBLIC;
 410
 411         sd->managedMem.mhe_UserData = sd;
 412
 413         sd->managedMem.mhe_Alloc = mh_Alloc;
 414         sd->managedMem.mhe_Free = mh_Free;
 415         sd->managedMem.mhe_AllocAbs = mh_AllocAbs;
 416         sd->managedMem.mhe_ReAlloc = mh_ReAlloc;
 417         sd->managedMem.mhe_Avail = mh_Avail;
 418
 419         Disable();
 420         AddTail(&SysBase->MemList, (struct Node *)&sd->managedMem);
 421         Enable();
 422     }
 423
 424     /* Number of ULONG's in bitmap */
 425     sd->CardMemSize = sd->Card.FbUsableSize >> 15;
 426
 427     bug("[ATIBMP] Bitmap at %p, size %d bytes (%d bits)\n", sd->CardMemBmp, sd->CardMemSize << 2, sd->Card.FbUsableSize >> 10);
 428 }
 429
 430 void BitmapFree(struct ati_staticdata *sd, ULONG ptr, ULONG size)
 431 {
 432     if (ptr + size < sd->Card.FbUsableSize)
 433     {
 434         bmclr(sd->CardMemBmp, sd->CardMemSize, ptr >> 10, (size + 1023) >> 10);
 435     }
 436 }
 437
 438 ULONG BitmapAlloc(struct ati_staticdata *sd, ULONG size)
 439 {
 440     ULONG ptr;
 441     size = (size + 1023) >> 10;
 442
 443     ptr = bmffz(sd->CardMemBmp, sd->CardMemSize, 0);
 444
 445     D(bug("[ATIBMP] BitmapAlloc(%d)\n", size));
 446
 447     while (ptr <= (sd->CardMemSize << 5) + size)
 448     {
 449         D(bug("[ATIBMP] ptr=%08x\n", ptr));
 450
 451         if (bmtstz(sd->CardMemBmp, ptr, size))
 452         {
 453             bmset(sd->CardMemBmp, sd->CardMemSize, ptr, size);
 454             break;
 455         }
 456
 457         ptr = bmffo(sd->CardMemBmp, sd->CardMemSize, ptr);
 458         ptr = bmffz(sd->CardMemBmp, sd->CardMemSize, ptr);
 459     }
 460
 461     if (ptr > (sd->CardMemSize << 5) - size)
 462         ptr = 0xffffffff;
 463     else
 464         ptr <<= 10;
 465
 466     return ptr;
 467 }