kernel/drivers/gpu/drm/omapdrm/tcm-sita.c

   1 /*
   2  * tcm-sita.c
   3  *
   4  * SImple Tiler Allocator (SiTA): 2D and 1D allocation(reservation) algorithm
   5  *
   6  * Authors: Ravi Ramachandra <r.ramachandra@ti.com>,
   7  *          Lajos Molnar <molnar@ti.com>
   8  *
   9  * Copyright (C) 2009-2010 Texas Instruments, Inc.
  10  *
  11  * This package is free software; you can redistribute it and/or modify
  12  * it under the terms of the GNU General Public License version 2 as
  13  * published by the Free Software Foundation.
  14  *
  15  * THIS PACKAGE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18  *
  19  */
  20 #include <linux/slab.h>
  21 #include <linux/spinlock.h>
  22
  23 #include "tcm-sita.h"
  24
  25 #define ALIGN_DOWN(value, align) ((value) & ~((align) - 1))
  26
  27 /* Individual selection criteria for different scan areas */
  28 static s32 CR_L2R_T2B = CR_BIAS_HORIZONTAL;
  29 static s32 CR_R2L_T2B = CR_DIAGONAL_BALANCE;
  30
  31 /*********************************************
  32  *      TCM API - Sita Implementation
  33  *********************************************/
  34 static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
  35                            struct tcm_area *area);
  36 static s32 sita_reserve_1d(struct tcm *tcm, u32 slots, struct tcm_area *area);
  37 static s32 sita_free(struct tcm *tcm, struct tcm_area *area);
  38 static void sita_deinit(struct tcm *tcm);
  39
  40 /*********************************************
  41  *      Main Scanner functions
  42  *********************************************/
  43 static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align,
  44                                    struct tcm_area *area);
  45
  46 static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
  47                         struct tcm_area *field, struct tcm_area *area);
  48
  49 static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
  50                         struct tcm_area *field, struct tcm_area *area);
  51
  52 static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
  53                         struct tcm_area *field, struct tcm_area *area);
  54
  55 /*********************************************
  56  *      Support Infrastructure Methods
  57  *********************************************/
  58 static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h);
  59
  60 static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
  61                             struct tcm_area *field, s32 criteria,
  62                             struct score *best);
  63
  64 static void get_nearness_factor(struct tcm_area *field,
  65                                 struct tcm_area *candidate,
  66                                 struct nearness_factor *nf);
  67
  68 static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
  69                                struct neighbor_stats *stat);
  70
  71 static void fill_area(struct tcm *tcm,
  72                                 struct tcm_area *area, struct tcm_area *parent);
  73
  74
  75 /*********************************************/
  76
  77 /*********************************************
  78  *      Utility Methods
  79  *********************************************/
  80 struct tcm *sita_init(u16 width, u16 height, struct tcm_pt *attr)
  81 {
  82         struct tcm *tcm;
  83         struct sita_pvt *pvt;
  84         struct tcm_area area = {0};
  85         s32 i;
  86
  87         if (width == 0 || height == 0)
  88                 return NULL;
  89
  90         tcm = kmalloc(sizeof(*tcm), GFP_KERNEL);
  91         pvt = kmalloc(sizeof(*pvt), GFP_KERNEL);
  92         if (!tcm || !pvt)
  93                 goto error;
  94
  95         memset(tcm, 0, sizeof(*tcm));
  96         memset(pvt, 0, sizeof(*pvt));
  97
  98         /* Updating the pointers to SiTA implementation APIs */
  99         tcm->height = height;
 100         tcm->width = width;
 101         tcm->reserve_2d = sita_reserve_2d;
 102         tcm->reserve_1d = sita_reserve_1d;
 103         tcm->free = sita_free;
 104         tcm->deinit = sita_deinit;
 105         tcm->pvt = (void *)pvt;
 106
 107         spin_lock_init(&(pvt->lock));
 108
 109         /* Creating tam map */
 110         pvt->map = kmalloc(sizeof(*pvt->map) * tcm->width, GFP_KERNEL);
 111         if (!pvt->map)
 112                 goto error;
 113
 114         for (i = 0; i < tcm->width; i++) {
 115                 pvt->map[i] =
 116                         kmalloc(sizeof(**pvt->map) * tcm->height,
 117                                                                 GFP_KERNEL);
 118                 if (pvt->map[i] == NULL) {
 119                         while (i--)
 120                                 kfree(pvt->map[i]);
 121                         kfree(pvt->map);
 122                         goto error;
 123                 }
 124         }
 125
 126         if (attr && attr->x <= tcm->width && attr->y <= tcm->height) {
 127                 pvt->div_pt.x = attr->x;
 128                 pvt->div_pt.y = attr->y;
 129
 130         } else {
 131                 /* Defaulting to 3:1 ratio on width for 2D area split */
 132                 /* Defaulting to 3:1 ratio on height for 2D and 1D split */
 133                 pvt->div_pt.x = (tcm->width * 3) / 4;
 134                 pvt->div_pt.y = (tcm->height * 3) / 4;
 135         }
 136
 137         spin_lock(&(pvt->lock));
 138         assign(&area, 0, 0, width - 1, height - 1);
 139         fill_area(tcm, &area, NULL);
 140         spin_unlock(&(pvt->lock));
 141         return tcm;
 142
 143 error:
 144         kfree(tcm);
 145         kfree(pvt);
 146         return NULL;
 147 }
 148
 149 static void sita_deinit(struct tcm *tcm)
 150 {
 151         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 152         struct tcm_area area = {0};
 153         s32 i;
 154
 155         area.p1.x = tcm->width - 1;
 156         area.p1.y = tcm->height - 1;
 157
 158         spin_lock(&(pvt->lock));
 159         fill_area(tcm, &area, NULL);
 160         spin_unlock(&(pvt->lock));
 161
 162         for (i = 0; i < tcm->height; i++)
 163                 kfree(pvt->map[i]);
 164         kfree(pvt->map);
 165         kfree(pvt);
 166 }
 167
 168 /**
 169  * Reserve a 1D area in the container
 170  *
 171  * @param num_slots     size of 1D area
 172  * @param area          pointer to the area that will be populated with the
 173  *                      reserved area
 174  *
 175  * @return 0 on success, non-0 error value on failure.
 176  */
 177 static s32 sita_reserve_1d(struct tcm *tcm, u32 num_slots,
 178                            struct tcm_area *area)
 179 {
 180         s32 ret;
 181         struct tcm_area field = {0};
 182         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 183
 184         spin_lock(&(pvt->lock));
 185
 186         /* Scanning entire container */
 187         assign(&field, tcm->width - 1, tcm->height - 1, 0, 0);
 188
 189         ret = scan_r2l_b2t_one_dim(tcm, num_slots, &field, area);
 190         if (!ret)
 191                 /* update map */
 192                 fill_area(tcm, area, area);
 193
 194         spin_unlock(&(pvt->lock));
 195         return ret;
 196 }
 197
 198 /**
 199  * Reserve a 2D area in the container
 200  *
 201  * @param w     width
 202  * @param h     height
 203  * @param area  pointer to the area that will be populated with the reserved
 204  *              area
 205  *
 206  * @return 0 on success, non-0 error value on failure.
 207  */
 208 static s32 sita_reserve_2d(struct tcm *tcm, u16 h, u16 w, u8 align,
 209                            struct tcm_area *area)
 210 {
 211         s32 ret;
 212         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 213
 214         /* not supporting more than 64 as alignment */
 215         if (align > 64)
 216                 return -EINVAL;
 217
 218         /* we prefer 1, 32 and 64 as alignment */
 219         align = align <= 1 ? 1 : align <= 32 ? 32 : 64;
 220
 221         spin_lock(&(pvt->lock));
 222         ret = scan_areas_and_find_fit(tcm, w, h, align, area);
 223         if (!ret)
 224                 /* update map */
 225                 fill_area(tcm, area, area);
 226
 227         spin_unlock(&(pvt->lock));
 228         return ret;
 229 }
 230
 231 /**
 232  * Unreserve a previously allocated 2D or 1D area
 233  * @param area  area to be freed
 234  * @return 0 - success
 235  */
 236 static s32 sita_free(struct tcm *tcm, struct tcm_area *area)
 237 {
 238         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 239
 240         spin_lock(&(pvt->lock));
 241
 242         /* check that this is in fact an existing area */
 243         WARN_ON(pvt->map[area->p0.x][area->p0.y] != area ||
 244                 pvt->map[area->p1.x][area->p1.y] != area);
 245
 246         /* Clear the contents of the associated tiles in the map */
 247         fill_area(tcm, area, NULL);
 248
 249         spin_unlock(&(pvt->lock));
 250
 251         return 0;
 252 }
 253
 254 /**
 255  * Note: In general the cordinates in the scan field area relevant to the can
 256  * sweep directions. The scan origin (e.g. top-left corner) will always be
 257  * the p0 member of the field.  Therfore, for a scan from top-left p0.x <= p1.x
 258  * and p0.y <= p1.y; whereas, for a scan from bottom-right p1.x <= p0.x and p1.y
 259  * <= p0.y
 260  */
 261
 262 /**
 263  * Raster scan horizontally right to left from top to bottom to find a place for
 264  * a 2D area of given size inside a scan field.
 265  *
 266  * @param w     width of desired area
 267  * @param h     height of desired area
 268  * @param align desired area alignment
 269  * @param area  pointer to the area that will be set to the best position
 270  * @param field area to scan (inclusive)
 271  *
 272  * @return 0 on success, non-0 error value on failure.
 273  */
 274 static s32 scan_r2l_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
 275                         struct tcm_area *field, struct tcm_area *area)
 276 {
 277         s32 x, y;
 278         s16 start_x, end_x, start_y, end_y, found_x = -1;
 279         struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
 280         struct score best = {{0}, {0}, {0}, 0};
 281
 282         start_x = field->p0.x;
 283         end_x = field->p1.x;
 284         start_y = field->p0.y;
 285         end_y = field->p1.y;
 286
 287         /* check scan area co-ordinates */
 288         if (field->p0.x < field->p1.x ||
 289             field->p1.y < field->p0.y)
 290                 return -EINVAL;
 291
 292         /* check if allocation would fit in scan area */
 293         if (w > LEN(start_x, end_x) || h > LEN(end_y, start_y))
 294                 return -ENOSPC;
 295
 296         /* adjust start_x and end_y, as allocation would not fit beyond */
 297         start_x = ALIGN_DOWN(start_x - w + 1, align); /* - 1 to be inclusive */
 298         end_y = end_y - h + 1;
 299
 300         /* check if allocation would still fit in scan area */
 301         if (start_x < end_x)
 302                 return -ENOSPC;
 303
 304         /* scan field top-to-bottom, right-to-left */
 305         for (y = start_y; y <= end_y; y++) {
 306                 for (x = start_x; x >= end_x; x -= align) {
 307                         if (is_area_free(map, x, y, w, h)) {
 308                                 found_x = x;
 309
 310                                 /* update best candidate */
 311                                 if (update_candidate(tcm, x, y, w, h, field,
 312                                                         CR_R2L_T2B, &best))
 313                                         goto done;
 314
 315                                 /* change upper x bound */
 316                                 end_x = x + 1;
 317                                 break;
 318                         } else if (map[x][y] && map[x][y]->is2d) {
 319                                 /* step over 2D areas */
 320                                 x = ALIGN(map[x][y]->p0.x - w + 1, align);
 321                         }
 322                 }
 323
 324                 /* break if you find a free area shouldering the scan field */
 325                 if (found_x == start_x)
 326                         break;
 327         }
 328
 329         if (!best.a.tcm)
 330                 return -ENOSPC;
 331 done:
 332         assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y);
 333         return 0;
 334 }
 335
 336 /**
 337  * Raster scan horizontally left to right from top to bottom to find a place for
 338  * a 2D area of given size inside a scan field.
 339  *
 340  * @param w     width of desired area
 341  * @param h     height of desired area
 342  * @param align desired area alignment
 343  * @param area  pointer to the area that will be set to the best position
 344  * @param field area to scan (inclusive)
 345  *
 346  * @return 0 on success, non-0 error value on failure.
 347  */
 348 static s32 scan_l2r_t2b(struct tcm *tcm, u16 w, u16 h, u16 align,
 349                         struct tcm_area *field, struct tcm_area *area)
 350 {
 351         s32 x, y;
 352         s16 start_x, end_x, start_y, end_y, found_x = -1;
 353         struct tcm_area ***map = ((struct sita_pvt *)tcm->pvt)->map;
 354         struct score best = {{0}, {0}, {0}, 0};
 355
 356         start_x = field->p0.x;
 357         end_x = field->p1.x;
 358         start_y = field->p0.y;
 359         end_y = field->p1.y;
 360
 361         /* check scan area co-ordinates */
 362         if (field->p1.x < field->p0.x ||
 363             field->p1.y < field->p0.y)
 364                 return -EINVAL;
 365
 366         /* check if allocation would fit in scan area */
 367         if (w > LEN(end_x, start_x) || h > LEN(end_y, start_y))
 368                 return -ENOSPC;
 369
 370         start_x = ALIGN(start_x, align);
 371
 372         /* check if allocation would still fit in scan area */
 373         if (w > LEN(end_x, start_x))
 374                 return -ENOSPC;
 375
 376         /* adjust end_x and end_y, as allocation would not fit beyond */
 377         end_x = end_x - w + 1; /* + 1 to be inclusive */
 378         end_y = end_y - h + 1;
 379
 380         /* scan field top-to-bottom, left-to-right */
 381         for (y = start_y; y <= end_y; y++) {
 382                 for (x = start_x; x <= end_x; x += align) {
 383                         if (is_area_free(map, x, y, w, h)) {
 384                                 found_x = x;
 385
 386                                 /* update best candidate */
 387                                 if (update_candidate(tcm, x, y, w, h, field,
 388                                                         CR_L2R_T2B, &best))
 389                                         goto done;
 390                                 /* change upper x bound */
 391                                 end_x = x - 1;
 392
 393                                 break;
 394                         } else if (map[x][y] && map[x][y]->is2d) {
 395                                 /* step over 2D areas */
 396                                 x = ALIGN_DOWN(map[x][y]->p1.x, align);
 397                         }
 398                 }
 399
 400                 /* break if you find a free area shouldering the scan field */
 401                 if (found_x == start_x)
 402                         break;
 403         }
 404
 405         if (!best.a.tcm)
 406                 return -ENOSPC;
 407 done:
 408         assign(area, best.a.p0.x, best.a.p0.y, best.a.p1.x, best.a.p1.y);
 409         return 0;
 410 }
 411
 412 /**
 413  * Raster scan horizontally right to left from bottom to top to find a place
 414  * for a 1D area of given size inside a scan field.
 415  *
 416  * @param num_slots     size of desired area
 417  * @param align         desired area alignment
 418  * @param area          pointer to the area that will be set to the best
 419  *                      position
 420  * @param field         area to scan (inclusive)
 421  *
 422  * @return 0 on success, non-0 error value on failure.
 423  */
 424 static s32 scan_r2l_b2t_one_dim(struct tcm *tcm, u32 num_slots,
 425                                 struct tcm_area *field, struct tcm_area *area)
 426 {
 427         s32 found = 0;
 428         s16 x, y;
 429         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 430         struct tcm_area *p;
 431
 432         /* check scan area co-ordinates */
 433         if (field->p0.y < field->p1.y)
 434                 return -EINVAL;
 435
 436         /**
 437          * Currently we only support full width 1D scan field, which makes sense
 438          * since 1D slot-ordering spans the full container width.
 439          */
 440         if (tcm->width != field->p0.x - field->p1.x + 1)
 441                 return -EINVAL;
 442
 443         /* check if allocation would fit in scan area */
 444         if (num_slots > tcm->width * LEN(field->p0.y, field->p1.y))
 445                 return -ENOSPC;
 446
 447         x = field->p0.x;
 448         y = field->p0.y;
 449
 450         /* find num_slots consecutive free slots to the left */
 451         while (found < num_slots) {
 452                 if (y < 0)
 453                         return -ENOSPC;
 454
 455                 /* remember bottom-right corner */
 456                 if (found == 0) {
 457                         area->p1.x = x;
 458                         area->p1.y = y;
 459                 }
 460
 461                 /* skip busy regions */
 462                 p = pvt->map[x][y];
 463                 if (p) {
 464                         /* move to left of 2D areas, top left of 1D */
 465                         x = p->p0.x;
 466                         if (!p->is2d)
 467                                 y = p->p0.y;
 468
 469                         /* start over */
 470                         found = 0;
 471                 } else {
 472                         /* count consecutive free slots */
 473                         found++;
 474                         if (found == num_slots)
 475                                 break;
 476                 }
 477
 478                 /* move to the left */
 479                 if (x == 0)
 480                         y--;
 481                 x = (x ? : tcm->width) - 1;
 482
 483         }
 484
 485         /* set top-left corner */
 486         area->p0.x = x;
 487         area->p0.y = y;
 488         return 0;
 489 }
 490
 491 /**
 492  * Find a place for a 2D area of given size inside a scan field based on its
 493  * alignment needs.
 494  *
 495  * @param w     width of desired area
 496  * @param h     height of desired area
 497  * @param align desired area alignment
 498  * @param area  pointer to the area that will be set to the best position
 499  *
 500  * @return 0 on success, non-0 error value on failure.
 501  */
 502 static s32 scan_areas_and_find_fit(struct tcm *tcm, u16 w, u16 h, u16 align,
 503                                    struct tcm_area *area)
 504 {
 505         s32 ret = 0;
 506         struct tcm_area field = {0};
 507         u16 boundary_x, boundary_y;
 508         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 509
 510         if (align > 1) {
 511                 /* prefer top-left corner */
 512                 boundary_x = pvt->div_pt.x - 1;
 513                 boundary_y = pvt->div_pt.y - 1;
 514
 515                 /* expand width and height if needed */
 516                 if (w > pvt->div_pt.x)
 517                         boundary_x = tcm->width - 1;
 518                 if (h > pvt->div_pt.y)
 519                         boundary_y = tcm->height - 1;
 520
 521                 assign(&field, 0, 0, boundary_x, boundary_y);
 522                 ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
 523
 524                 /* scan whole container if failed, but do not scan 2x */
 525                 if (ret != 0 && (boundary_x != tcm->width - 1 ||
 526                                  boundary_y != tcm->height - 1)) {
 527                         /* scan the entire container if nothing found */
 528                         assign(&field, 0, 0, tcm->width - 1, tcm->height - 1);
 529                         ret = scan_l2r_t2b(tcm, w, h, align, &field, area);
 530                 }
 531         } else if (align == 1) {
 532                 /* prefer top-right corner */
 533                 boundary_x = pvt->div_pt.x;
 534                 boundary_y = pvt->div_pt.y - 1;
 535
 536                 /* expand width and height if needed */
 537                 if (w > (tcm->width - pvt->div_pt.x))
 538                         boundary_x = 0;
 539                 if (h > pvt->div_pt.y)
 540                         boundary_y = tcm->height - 1;
 541
 542                 assign(&field, tcm->width - 1, 0, boundary_x, boundary_y);
 543                 ret = scan_r2l_t2b(tcm, w, h, align, &field, area);
 544
 545                 /* scan whole container if failed, but do not scan 2x */
 546                 if (ret != 0 && (boundary_x != 0 ||
 547                                  boundary_y != tcm->height - 1)) {
 548                         /* scan the entire container if nothing found */
 549                         assign(&field, tcm->width - 1, 0, 0, tcm->height - 1);
 550                         ret = scan_r2l_t2b(tcm, w, h, align, &field,
 551                                            area);
 552                 }
 553         }
 554
 555         return ret;
 556 }
 557
 558 /* check if an entire area is free */
 559 static s32 is_area_free(struct tcm_area ***map, u16 x0, u16 y0, u16 w, u16 h)
 560 {
 561         u16 x = 0, y = 0;
 562         for (y = y0; y < y0 + h; y++) {
 563                 for (x = x0; x < x0 + w; x++) {
 564                         if (map[x][y])
 565                                 return false;
 566                 }
 567         }
 568         return true;
 569 }
 570
 571 /* fills an area with a parent tcm_area */
 572 static void fill_area(struct tcm *tcm, struct tcm_area *area,
 573                         struct tcm_area *parent)
 574 {
 575         s32 x, y;
 576         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 577         struct tcm_area a, a_;
 578
 579         /* set area's tcm; otherwise, enumerator considers it invalid */
 580         area->tcm = tcm;
 581
 582         tcm_for_each_slice(a, *area, a_) {
 583                 for (x = a.p0.x; x <= a.p1.x; ++x)
 584                         for (y = a.p0.y; y <= a.p1.y; ++y)
 585                                 pvt->map[x][y] = parent;
 586
 587         }
 588 }
 589
 590 /**
 591  * Compares a candidate area to the current best area, and if it is a better
 592  * fit, it updates the best to this one.
 593  *
 594  * @param x0, y0, w, h          top, left, width, height of candidate area
 595  * @param field                 scan field
 596  * @param criteria              scan criteria
 597  * @param best                  best candidate and its scores
 598  *
 599  * @return 1 (true) if the candidate area is known to be the final best, so no
 600  * more searching should be performed
 601  */
 602 static s32 update_candidate(struct tcm *tcm, u16 x0, u16 y0, u16 w, u16 h,
 603                             struct tcm_area *field, s32 criteria,
 604                             struct score *best)
 605 {
 606         struct score me;        /* score for area */
 607
 608         /*
 609          * NOTE: For horizontal bias we always give the first found, because our
 610          * scan is horizontal-raster-based and the first candidate will always
 611          * have the horizontal bias.
 612          */
 613         bool first = criteria & CR_BIAS_HORIZONTAL;
 614
 615         assign(&me.a, x0, y0, x0 + w - 1, y0 + h - 1);
 616
 617         /* calculate score for current candidate */
 618         if (!first) {
 619                 get_neighbor_stats(tcm, &me.a, &me.n);
 620                 me.neighs = me.n.edge + me.n.busy;
 621                 get_nearness_factor(field, &me.a, &me.f);
 622         }
 623
 624         /* the 1st candidate is always the best */
 625         if (!best->a.tcm)
 626                 goto better;
 627
 628         BUG_ON(first);
 629
 630         /* diagonal balance check */
 631         if ((criteria & CR_DIAGONAL_BALANCE) &&
 632                 best->neighs <= me.neighs &&
 633                 (best->neighs < me.neighs ||
 634                  /* this implies that neighs and occupied match */
 635                  best->n.busy < me.n.busy ||
 636                  (best->n.busy == me.n.busy &&
 637                   /* check the nearness factor */
 638                   best->f.x + best->f.y > me.f.x + me.f.y)))
 639                 goto better;
 640
 641         /* not better, keep going */
 642         return 0;
 643
 644 better:
 645         /* save current area as best */
 646         memcpy(best, &me, sizeof(me));
 647         best->a.tcm = tcm;
 648         return first;
 649 }
 650
 651 /**
 652  * Calculate the nearness factor of an area in a search field.  The nearness
 653  * factor is smaller if the area is closer to the search origin.
 654  */
 655 static void get_nearness_factor(struct tcm_area *field, struct tcm_area *area,
 656                                 struct nearness_factor *nf)
 657 {
 658         /**
 659          * Using signed math as field coordinates may be reversed if
 660          * search direction is right-to-left or bottom-to-top.
 661          */
 662         nf->x = (s32)(area->p0.x - field->p0.x) * 1000 /
 663                 (field->p1.x - field->p0.x);
 664         nf->y = (s32)(area->p0.y - field->p0.y) * 1000 /
 665                 (field->p1.y - field->p0.y);
 666 }
 667
 668 /* get neighbor statistics */
 669 static void get_neighbor_stats(struct tcm *tcm, struct tcm_area *area,
 670                          struct neighbor_stats *stat)
 671 {
 672         s16 x = 0, y = 0;
 673         struct sita_pvt *pvt = (struct sita_pvt *)tcm->pvt;
 674
 675         /* Clearing any exisiting values */
 676         memset(stat, 0, sizeof(*stat));
 677
 678         /* process top & bottom edges */
 679         for (x = area->p0.x; x <= area->p1.x; x++) {
 680                 if (area->p0.y == 0)
 681                         stat->edge++;
 682                 else if (pvt->map[x][area->p0.y - 1])
 683                         stat->busy++;
 684
 685                 if (area->p1.y == tcm->height - 1)
 686                         stat->edge++;
 687                 else if (pvt->map[x][area->p1.y + 1])
 688                         stat->busy++;
 689         }
 690
 691         /* process left & right edges */
 692         for (y = area->p0.y; y <= area->p1.y; ++y) {
 693                 if (area->p0.x == 0)
 694                         stat->edge++;
 695                 else if (pvt->map[area->p0.x - 1][y])
 696                         stat->busy++;
 697
 698                 if (area->p1.x == tcm->width - 1)
 699                         stat->edge++;
 700                 else if (pvt->map[area->p1.x + 1][y])
 701                         stat->busy++;
 702         }
 703 }