#include <stdio.h></stdio.h>

#include <stdlib.h></stdlib.h>

#include <string.h></string.h>

#include <assert.h></assert.h>

#include "traster.h"

/*

#include "img.h"

#include "file.h"

#include "toonz.h"

#include "raster.h"

#include "tmsg.h"

#include "copP.h"*/

/*------------------------------------------------------------------------*/

namespace {

UCHAR First_preseed_table[256] = {

    8, 0, 1, 0, 2, 2, 1, 0, 3, 3, 3, 3, 2, 2, 3, 3, 4, 4, 1, 0, 2, 2, 1, 0,

    4, 4, 3, 3, 2, 2, 3, 3, 5, 5, 1, 5, 2, 2, 1, 5, 5, 5, 5, 5, 2, 2, 5, 5,

    4, 4, 1, 5, 2, 2, 1, 5, 4, 4, 5, 5, 2, 2, 5, 5, 6, 6, 1, 6, 2, 2, 1, 6,

    6, 6, 6, 6, 2, 2, 6, 6, 4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 8, 8, 2, 2, 8, 8,

    6, 6, 1, 6, 2, 2, 1, 6, 6, 6, 6, 6, 2, 2, 6, 6, 4, 4, 1, 0, 2, 2, 1, 0,

    4, 4, 8, 8, 2, 2, 8, 8, 7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7,

    4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 3, 3, 2, 2, 3, 3, 7, 7, 1, 7, 2, 2, 1, 7,

    7, 7, 7, 7, 2, 2, 7, 7, 4, 4, 1, 5, 2, 2, 1, 5, 4, 4, 5, 5, 2, 2, 5, 5,

    7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7, 4, 4, 1, 0, 2, 2, 1, 0,

    4, 4, 8, 8, 2, 2, 8, 8, 7, 7, 1, 7, 2, 2, 1, 7, 7, 7, 7, 7, 2, 2, 7, 7,

    4, 4, 1, 0, 2, 2, 1, 0, 4, 4, 8, 8, 2, 2, 8, 8};

static UCHAR Next_point_table[2048] = {

    8, 8, 8, 8, 8, 8, 8, 8, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1,

    0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 0, 0, 2, 2, 2, 2, 2, 2, 2,

    1, 2, 2, 2, 2, 2, 2, 0, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0,

    0, 0, 0, 0, 0, 3, 3, 1, 1, 1, 1, 1, 1, 3, 0, 1, 1, 1, 1, 1, 1, 3, 3, 3, 2,

    2, 2, 2, 2, 3, 0, 0, 2, 2, 2, 2, 2, 3, 3, 1, 2, 2, 2, 2, 2, 3, 0, 1, 2, 2,

    2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 4, 0, 4, 4, 4, 4, 4, 1, 4, 1, 4,

    4, 4, 4, 0, 1, 4, 1, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 0, 0, 4, 2, 4, 4,

    4, 4, 4, 1, 4, 2, 4, 4, 4, 4, 0, 1, 4, 2, 4, 4, 4, 3, 3, 3, 4, 3, 4, 4, 4,

    3, 0, 0, 4, 0, 4, 4, 4, 3, 3, 1, 4, 1, 4, 4, 4, 3, 0, 1, 4, 1, 4, 4, 4, 3,

    3, 3, 4, 2, 4, 4, 4, 3, 0, 0, 4, 2, 4, 4, 4, 3, 3, 1, 4, 2, 4, 4, 4, 3, 0,

    1, 4, 2, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 0, 0, 5, 0, 0, 0, 0, 5, 5, 1,

    5, 1, 1, 1, 1, 5, 0, 1, 5, 1, 1, 1, 1, 5, 5, 5, 5, 2, 2, 2, 2, 5, 0, 0, 5,

    2, 2, 2, 2, 5, 5, 1, 5, 2, 2, 2, 2, 5, 0, 1, 5, 2, 2, 2, 2, 3, 3, 3, 5, 3,

    3, 3, 3, 3, 0, 0, 5, 0, 0, 0, 0, 3, 3, 1, 5, 1, 1, 1, 1, 3, 0, 1, 5, 1, 1,

    1, 1, 3, 3, 3, 5, 2, 2, 2, 2, 3, 0, 0, 5, 2, 2, 2, 2, 3, 3, 1, 5, 2, 2, 2,

    2, 3, 0, 1, 5, 2, 2, 2, 2, 5, 5, 5, 5, 5, 4, 4, 4, 5, 0, 0, 5, 0, 4, 4, 4,

    5, 5, 1, 5, 1, 4, 4, 4, 5, 0, 1, 5, 1, 4, 4, 4, 5, 5, 5, 5, 2, 4, 4, 4, 5,

    0, 0, 5, 2, 4, 4, 4, 5, 5, 1, 5, 2, 4, 4, 4, 5, 0, 1, 5, 2, 4, 4, 4, 3, 3,

    3, 5, 3, 4, 4, 4, 3, 0, 0, 5, 0, 4, 4, 4, 3, 3, 1, 5, 1, 4, 4, 4, 3, 0, 1,

    5, 1, 4, 4, 4, 3, 3, 3, 5, 2, 4, 4, 4, 3, 0, 0, 5, 2, 4, 4, 4, 3, 3, 1, 5,

    2, 4, 4, 4, 3, 0, 1, 5, 2, 4, 4, 4, 6, 6, 6, 6, 6, 6, 6, 6, 6, 0, 0, 6, 0,

    6, 0, 0, 6, 6, 1, 6, 1, 6, 1, 1, 6, 0, 1, 6, 1, 6, 1, 1, 6, 6, 6, 6, 2, 6,

    2, 2, 6, 0, 0, 6, 2, 6, 2, 2, 6, 6, 1, 6, 2, 6, 2, 2, 6, 0, 1, 6, 2, 6, 2,

    2, 3, 3, 3, 6, 3, 6, 3, 3, 3, 0, 0, 6, 0, 6, 0, 0, 3, 3, 1, 6, 1, 6, 1, 1,

    3, 0, 1, 6, 1, 6, 1, 1, 3, 3, 3, 6, 2, 6, 2, 2, 3, 0, 0, 6, 2, 6, 2, 2, 3,

    3, 1, 6, 2, 6, 2, 2, 3, 0, 1, 6, 2, 6, 2, 2, 6, 6, 6, 6, 6, 6, 4, 4, 6, 0,

    0, 6, 0, 6, 4, 4, 6, 6, 1, 6, 1, 6, 4, 4, 6, 0, 1, 6, 1, 6, 4, 4, 6, 6, 6,

    6, 2, 6, 4, 4, 6, 0, 0, 6, 2, 6, 4, 4, 6, 6, 1, 6, 2, 6, 4, 4, 6, 0, 1, 6,

    2, 6, 4, 4, 3, 3, 3, 6, 3, 6, 4, 4, 3, 0, 0, 6, 0, 6, 4, 4, 3, 3, 1, 6, 1,

    6, 4, 4, 3, 0, 1, 6, 1, 6, 4, 4, 3, 3, 3, 6, 2, 6, 4, 4, 3, 0, 0, 6, 2, 6,

    4, 4, 3, 3, 1, 6, 2, 6, 4, 4, 3, 0, 1, 6, 2, 6, 4, 4, 5, 5, 5, 5, 5, 6, 5,

    5, 5, 0, 0, 5, 0, 6, 0, 0, 5, 5, 1, 5, 1, 6, 1, 1, 5, 0, 1, 5, 1, 6, 1, 1,

    5, 5, 5, 5, 2, 6, 2, 2, 5, 0, 0, 5, 2, 6, 2, 2, 5, 5, 1, 5, 2, 6, 2, 2, 5,

    0, 1, 5, 2, 6, 2, 2, 3, 3, 3, 5, 3, 6, 3, 3, 3, 0, 0, 5, 0, 6, 0, 0, 3, 3,

    1, 5, 1, 6, 1, 1, 3, 0, 1, 5, 1, 6, 1, 1, 3, 3, 3, 5, 2, 6, 2, 2, 3, 0, 0,

    5, 2, 6, 2, 2, 3, 3, 1, 5, 2, 6, 2, 2, 3, 0, 1, 5, 2, 6, 2, 2, 5, 5, 5, 5,

    5, 6, 4, 4, 5, 0, 0, 5, 0, 6, 4, 4, 5, 5, 1, 5, 1, 6, 4, 4, 5, 0, 1, 5, 1,

    6, 4, 4, 5, 5, 5, 5, 2, 6, 4, 4, 5, 0, 0, 5, 2, 6, 4, 4, 5, 5, 1, 5, 2, 6,

    4, 4, 5, 0, 1, 5, 2, 6, 4, 4, 3, 3, 3, 5, 3, 6, 4, 4, 3, 0, 0, 5, 0, 6, 4,

    4, 3, 3, 1, 5, 1, 6, 4, 4, 3, 0, 1, 5, 1, 6, 4, 4, 3, 3, 3, 5, 2, 6, 4, 4,

    3, 0, 0, 5, 2, 6, 4, 4, 3, 3, 1, 5, 2, 6, 4, 4, 3, 0, 1, 5, 2, 6, 4, 4, 7,

    7, 7, 7, 7, 7, 7, 7, 7, 0, 0, 7, 0, 7, 7, 0, 7, 7, 1, 7, 1, 7, 7, 1, 7, 0,

    1, 7, 1, 7, 7, 1, 7, 7, 7, 7, 2, 7, 7, 2, 7, 0, 0, 7, 2, 7, 7, 2, 7, 7, 1,

    7, 2, 7, 7, 2, 7, 0, 1, 7, 2, 7, 7, 2, 3, 3, 3, 7, 3, 7, 7, 3, 3, 0, 0, 7,

    0, 7, 7, 0, 3, 3, 1, 7, 1, 7, 7, 1, 3, 0, 1, 7, 1, 7, 7, 1, 3, 3, 3, 7, 2,

    7, 7, 2, 3, 0, 0, 7, 2, 7, 7, 2, 3, 3, 1, 7, 2, 7, 7, 2, 3, 0, 1, 7, 2, 7,

    7, 2, 7, 7, 7, 7, 7, 7, 7, 4, 7, 0, 0, 7, 0, 7, 7, 4, 7, 7, 1, 7, 1, 7, 7,

    4, 7, 0, 1, 7, 1, 7, 7, 4, 7, 7, 7, 7, 2, 7, 7, 4, 7, 0, 0, 7, 2, 7, 7, 4,

    7, 7, 1, 7, 2, 7, 7, 4, 7, 0, 1, 7, 2, 7, 7, 4, 3, 3, 3, 7, 3, 7, 7, 4, 3,

    0, 0, 7, 0, 7, 7, 4, 3, 3, 1, 7, 1, 7, 7, 4, 3, 0, 1, 7, 1, 7, 7, 4, 3, 3,

    3, 7, 2, 7, 7, 4, 3, 0, 0, 7, 2, 7, 7, 4, 3, 3, 1, 7, 2, 7, 7, 4, 3, 0, 1,

    7, 2, 7, 7, 4, 5, 5, 5, 5, 5, 7, 7, 5, 5, 0, 0, 5, 0, 7, 7, 0, 5, 5, 1, 5,

    1, 7, 7, 1, 5, 0, 1, 5, 1, 7, 7, 1, 5, 5, 5, 5, 2, 7, 7, 2, 5, 0, 0, 5, 2,

    7, 7, 2, 5, 5, 1, 5, 2, 7, 7, 2, 5, 0, 1, 5, 2, 7, 7, 2, 3, 3, 3, 5, 3, 7,

    7, 3, 3, 0, 0, 5, 0, 7, 7, 0, 3, 3, 1, 5, 1, 7, 7, 1, 3, 0, 1, 5, 1, 7, 7,

    1, 3, 3, 3, 5, 2, 7, 7, 2, 3, 0, 0, 5, 2, 7, 7, 2, 3, 3, 1, 5, 2, 7, 7, 2,

    3, 0, 1, 5, 2, 7, 7, 2, 5, 5, 5, 5, 5, 7, 7, 4, 5, 0, 0, 5, 0, 7, 7, 4, 5,

    5, 1, 5, 1, 7, 7, 4, 5, 0, 1, 5, 1, 7, 7, 4, 5, 5, 5, 5, 2, 7, 7, 4, 5, 0,

    0, 5, 2, 7, 7, 4, 5, 5, 1, 5, 2, 7, 7, 4, 5, 0, 1, 5, 2, 7, 7, 4, 3, 3, 3,

    5, 3, 7, 7, 4, 3, 0, 0, 5, 0, 7, 7, 4, 3, 3, 1, 5, 1, 7, 7, 4, 3, 0, 1, 5,

    1, 7, 7, 4, 3, 3, 3, 5, 2, 7, 7, 4, 3, 0, 0, 5, 2, 7, 7, 4, 3, 3, 1, 5, 2,

    7, 7, 4, 3, 0, 1, 5, 2, 7, 7, 4, 6, 6, 6, 6, 6, 6, 7, 6, 6, 0, 0, 6, 0, 6,

    7, 0, 6, 6, 1, 6, 1, 6, 7, 1, 6, 0, 1, 6, 1, 6, 7, 1, 6, 6, 6, 6, 2, 6, 7,

    2, 6, 0, 0, 6, 2, 6, 7, 2, 6, 6, 1, 6, 2, 6, 7, 2, 6, 0, 1, 6, 2, 6, 7, 2,

    3, 3, 3, 6, 3, 6, 7, 3, 3, 0, 0, 6, 0, 6, 7, 0, 3, 3, 1, 6, 1, 6, 7, 1, 3,

    0, 1, 6, 1, 6, 7, 1, 3, 3, 3, 6, 2, 6, 7, 2, 3, 0, 0, 6, 2, 6, 7, 2, 3, 3,

    1, 6, 2, 6, 7, 2, 3, 0, 1, 6, 2, 6, 7, 2, 6, 6, 6, 6, 6, 6, 7, 4, 6, 0, 0,

    6, 0, 6, 7, 4, 6, 6, 1, 6, 1, 6, 7, 4, 6, 0, 1, 6, 1, 6, 7, 4, 6, 6, 6, 6,

    2, 6, 7, 4, 6, 0, 0, 6, 2, 6, 7, 4, 6, 6, 1, 6, 2, 6, 7, 4, 6, 0, 1, 6, 2,

    6, 7, 4, 3, 3, 3, 6, 3, 6, 7, 4, 3, 0, 0, 6, 0, 6, 7, 4, 3, 3, 1, 6, 1, 6,

    7, 4, 3, 0, 1, 6, 1, 6, 7, 4, 3, 3, 3, 6, 2, 6, 7, 4, 3, 0, 0, 6, 2, 6, 7,

    4, 3, 3, 1, 6, 2, 6, 7, 4, 3, 0, 1, 6, 2, 6, 7, 4, 5, 5, 5, 5, 5, 6, 7, 5,

    5, 0, 0, 5, 0, 6, 7, 0, 5, 5, 1, 5, 1, 6, 7, 1, 5, 0, 1, 5, 1, 6, 7, 1, 5,

    5, 5, 5, 2, 6, 7, 2, 5, 0, 0, 5, 2, 6, 7, 2, 5, 5, 1, 5, 2, 6, 7, 2, 5, 0,

    1, 5, 2, 6, 7, 2, 3, 3, 3, 5, 3, 6, 7, 3, 3, 0, 0, 5, 0, 6, 7, 0, 3, 3, 1,

    5, 1, 6, 7, 1, 3, 0, 1, 5, 1, 6, 7, 1, 3, 3, 3, 5, 2, 6, 7, 2, 3, 0, 0, 5,

    2, 6, 7, 2, 3, 3, 1, 5, 2, 6, 7, 2, 3, 0, 1, 5, 2, 6, 7, 2, 5, 5, 5, 5, 5,

    6, 7, 4, 5, 0, 0, 5, 0, 6, 7, 4, 5, 5, 1, 5, 1, 6, 7, 4, 5, 0, 1, 5, 1, 6,

    7, 4, 5, 5, 5, 5, 2, 6, 7, 4, 5, 0, 0, 5, 2, 6, 7, 4, 5, 5, 1, 5, 2, 6, 7,

    4, 5, 0, 1, 5, 2, 6, 7, 4, 3, 3, 3, 5, 3, 6, 7, 4, 3, 0, 0, 5, 0, 6, 7, 4,

    3, 3, 1, 5, 1, 6, 7, 4, 3, 0, 1, 5, 1, 6, 7, 4, 3, 3, 3, 5, 2, 6, 7, 4, 3,

    0, 0, 5, 2, 6, 7, 4, 3, 3, 1, 5, 2, 6, 7, 4, 3, 0, 1, 5, 2, 6, 7, 4};

/*------------------------------------------------------------------------*/

int Lx;

int Displace_vector[8];

#define E_PIX(pix) (*(pix + 1))

#define W_PIX(pix) (*(pix - 1))

#define N_PIX(pix) (*(pix + Lx))

#define S_PIX(pix) (*(pix - Lx))

#define SW_PIX(pix) (*(pix - Lx - 1))

#define NW_PIX(pix) (*(pix + Lx - 1))

#define NE_PIX(pix) (*(pix + Lx + 1))

#define SE_PIX(pix) (*(pix - Lx + 1))

#define NEIGHBOURS_CODE(pix)                                                   \

  (((SW_PIX(pix) != 0) << 0) | ((S_PIX(pix) != 0) << 1) |                      \

   ((SE_PIX(pix) != 0) << 2) | ((W_PIX(pix) != 0) << 3) |                      \

   ((E_PIX(pix) != 0) << 4) | ((NW_PIX(pix) != 0) << 5) |                      \

   ((N_PIX(pix) != 0) << 6) | ((NE_PIX(pix) != 0) << 7))

/*------------------------------------------------------------------------*/

#define FIRST_PRESEED(code) First_preseed_table[code]

/*------------------------------------------------------------------------*/

#define NEXT_POINT(code, preseed) Next_point_table[(code << 3) | preseed]

/*------------------------------------------------------------------------*/

#define UPDATE_POS(displ_code, x_pos, y_pos)                                   \

  switch (displ_code) {                                                        \

  case 0:                                                                      \

    x_pos--;                                                                   \

    y_pos--;                                                                   \

    break;                                                                     \

  case 1:                                                                      \

    y_pos--;                                                                   \

    break;                                                                     \

  case 2:                                                                      \

    x_pos++;                                                                   \

    y_pos--;                                                                   \

    break;                                                                     \

  case 3:                                                                      \

    x_pos--;                                                                   \

    break;                                                                     \

  case 4:                                                                      \

    x_pos++;                                                                   \

    break;                                                                     \

  case 5:                                                                      \

    x_pos--;                                                                   \

    y_pos++;                                                                   \

    break;                                                                     \

  case 6:                                                                      \

    y_pos++;                                                                   \

    break;                                                                     \

  case 7:                                                                      \

    x_pos++;                                                                   \

    y_pos++;                                                                   \

    break;                                                                     \

  default:                                                                     \

    assert(false);                                                             \

  }

/*------------------------------------------------------------------------*/

/*=============================================================================*/

/*---------------------------------------------------------------------------*/

static int fillByteRaster(const TRaster32P &rin, TRasterGR8P &rout) {

  bool ret = false;

  assert(rin->getLx() == rout->getLx() - 2 &&

         rin->getLy() == rout->getLy() - 2);

  memset(rout->getRawData(), 0, rout->getLx() * rout->getLy());

  for (int i = 0; i < rin->getLy(); i++) {

    TPixel32 *bufIn = (TPixel32 *)rin->getRawData() + i * rin->getWrap();

    UCHAR *bufOut = (UCHAR *)rout->getRawData() + (i + 1) * rout->getWrap() + 1;

    for (int j = 0; j < rin->getLx(); j++, bufIn++, bufOut++)

      if (bufIn->m != 0) {

        ret     = true;

        *bufOut = 1;

      }

  }

  return ret;

}

/*---------------------------------------------------------------------------*/

static void initialize_displace_vector(void) {

  Displace_vector[0] = -Lx - 1;

  Displace_vector[1] = -Lx;

  Displace_vector[2] = -Lx + 1;

  Displace_vector[3] = -1;

  Displace_vector[4] = +1;

  Displace_vector[5] = Lx - 1;

  Displace_vector[6] = Lx;

  Displace_vector[7] = Lx + 1;

}

/*------------------------------------------------------------------------*/

static int find_next_seed(const TRasterGR8P &r, bool first_seed, UCHAR *&seed,

                          int &x_pos, int &y_pos) {

  static int Curr_x = 0, Curr_y = 0;

  UCHAR *pix;

  if (first_seed) {

    Curr_x = 0;

    Curr_y = 0;

  }

  seed = 0;

  for (; Curr_y < r->getLy(); Curr_y++) {

    pix = (UCHAR *)r->getRawData() + Curr_y * r->getWrap() + Curr_x;

    for (; Curr_x < r->getLx(); Curr_x++, pix++)

      if (*pix == 1 &&

          (!E_PIX(pix) || !W_PIX(pix) || !N_PIX(pix) || !S_PIX(pix))) {

        seed  = pix;

        x_pos = Curr_x;

        y_pos = Curr_y;

        return true;

      }

    Curr_x = 0;

  }

  return false;

}

/*------------------------------------------------------------------------*/

#define COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)                    \

  {                                                                            \

    aux = old_x_pos * y_pos - x_pos * old_y_pos;                               \

    den += aux;                                                                \

    x_num += (x_pos + old_x_pos) * aux;                                        \

    y_num += (y_pos + old_y_pos) * aux;                                        \

  }

/*------------------------------------------------------------------------*/

static void doComputeCentroid(const TRasterGR8P &r, TPoint &cp) {

  int preseed, displ, prewalker, code;

  UCHAR *seed, *walker;

  int x_num = 0, y_num = 0, den = 0;

  int x_pos, y_pos, old_x_pos, old_y_pos;

  int aux, old_displ = -1;

  bool first_seed;

  Lx                 = r->getLx();

  Displace_vector[0] = -Lx - 1;

  Displace_vector[1] = -Lx;

  Displace_vector[2] = -Lx + 1;

  Displace_vector[3] = -1;

  Displace_vector[4] = +1;

  Displace_vector[5] = Lx - 1;

  Displace_vector[6] = Lx;

  Displace_vector[7] = Lx + 1;

  first_seed = true;

  while (find_next_seed(r, first_seed, seed, x_pos, y_pos)) {

    first_seed = false;

    *seed |= 0x2;

    code    = NEIGHBOURS_CODE(seed);

    preseed = FIRST_PRESEED(code);

    if (preseed == 8) continue;

    displ = NEXT_POINT(code, preseed);

    walker = seed + Displace_vector[displ];

    old_x_pos = x_pos;

    old_y_pos = y_pos;

    UPDATE_POS(displ, x_pos, y_pos)

    COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)

    prewalker = displ ^ 0x7;

    while ((walker != seed) || (preseed != prewalker)) {

      *walker |= 0x2;

      displ = NEXT_POINT(NEIGHBOURS_CODE(walker), prewalker);

      walker += Displace_vector[displ];

      old_x_pos = x_pos;

      old_y_pos = y_pos;

      UPDATE_POS(displ, x_pos, y_pos)

      COMPUTE_NUM_DEN(x_pos, y_pos, old_x_pos, old_y_pos)

      prewalker = displ ^ 0x7;

    }

  }

  if (den)

    cp = TPoint(tround(x_num / (3.0 * den)), tround(y_num / (3.0 * den)));

}

}  // namespace

TPoint computeCentroid(const TRaster32P &r) {

  TPoint ret(1, 1);

  TRasterGR8P raux(r->getLx() + 2, r->getLy() + 2);

  if (fillByteRaster(r, raux)) doComputeCentroid(raux, ret);

  ret.x--;

  ret.y--; /* per il bordo aggiunto */

  return ret;

}