/* $Id: imagebox.c,v 1.11 1998/03/04 20:53:08 shipeng Exp $ */
/****************************************************************************/
/*   MPEG4 Visual Texture Coding (VTC) Mode Software                        */
/*                                                                          */
/*   This software was developed by                                         */
/*   Sarnoff Coporation                   and    Texas Instruments          */
/*   Iraj Sodagar   (iraj@sarnoff.com)           Jie Liang (liang@ti.com)   */
/*   Hung-Ju Lee    (hjlee@sarnoff.com)                                     */
/*   Paul Hatrack   (hatrack@sarnoff.com)                                   */
/*   Shipeng Li     (shipeng@sarnoff.com)                                   */
/*   Bing-Bing Chai (bchai@sarnoff.com)                                     */
/*                                                                          */
/* In the course of development of the MPEG-4 standard. This software       */
/* module is an implementation of a part of one or more MPEG-4 tools as     */
/* specified by the MPEG-4 standard.                                        */
/*                                                                          */
/* The copyright of this software belongs to ISO/IEC. ISO/IEC gives use     */
/* of the MPEG-4 standard free license to use this  software module or      */
/* modifications thereof for hardware or software products claiming         */
/* conformance to the MPEG-4 standard.                                      */
/*                                                                          */
/* Those intending to use this software module in hardware or software      */
/* products are advised that use may infringe existing  patents. The        */
/* original developers of this software module and their companies, the     */
/* subsequent editors and their companies, and ISO/IEC have no liability    */
/* and ISO/IEC have no liability for use of this software module or         */
/* modification thereof in an implementation.                               */
/*                                                                          */
/* Permission is granted to MPEG memebers to use, copy, modify,             */
/* and distribute the software modules ( or portions thereof )              */
/* for standardization activity within ISO/IEC JTC1/SC29/WG11.              */
/*                                                                          */
/* Copyright (C) 1998  Sarnoff Coporation and Texas Instruments             */ 
/****************************************************************************/

/************************************************************/
/*     Sarnoff Very Low Bit Rate Still Image Coder          */
/*     Copyright 1995, 1996, 1997, 1998 Sarnoff Corporation */
/************************************************************/

/* imagebox.c -- extend/crop an image to a box of the minimal multiples of 
                 2^Decomposition Level size that contains the object, according
		 to the mask information */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <memory.h>
#include "dwt.h"

static Int LCM(Int x, Int y);
static Int GCD(Int x, Int y);


/* Function: GetBox()
   Description: get the bounding box of the image object
   Input:
   
   InImage -- Input image data, data type defined by DataType;
   InMask -- Input image mask, can be NULL if Shape == VTC_RECTANGULAR;
   RealWidth, RealHeight  -- the size of the actual image;
   Nx, Ny -- specify  that OriginX and OriginY must be multiple of Nx and Ny
             to accomdate different color compoents configuration:
	     Examples:
	     for 420:   Nx  Ny 
	           Y:   2   2
                   U,V: 1   1
	     for 422:   
	           Y:   2   1
             for 444:
	      Y,U,V:    1   1
	     for mono:
                  Y:    1   1
	     for YUV9:  
                  Y:    4   4
                  U,V:  1   1  
  
   DataType -- 0 - unsigned char 1- unsigned short for InImage and OutImage
   Shape   -- if -1, the SHAPE is rectangular, else arbitary shape and
              Shape defines the mask value of an object, useful for
	      multiple objects coding 
   nLevels -- levels of decomposition
   Output:
   
   OutImage -- Output image within the bounding box (can be cropped or 
               extended version of the InImage)
   OutMask -- Output image mask, extended area is marked as Don't-care
   VirtualWidth, VirtualHeight -- size of the output image
   OriginX, OriginY -- origins of the output image relative to the original
                       image
		       
   Return:  DWT_NOVALID_PIXEL if the mask are all zeros, otherwise DWT_OK 
            if no error;	       
   Note: The caller should free the memory OutImage and OutMask allocated by this program 
         after it finishes using them.
*/

Int GetBox(Void *InImage, UChar *InMask, Void **OutImage, UChar **OutMask, 
	   Int RealWidth, Int RealHeight, 
	   Int Nx, Int Ny,
	   Int *VirtualWidth, Int *VirtualHeight, 
	   Int *OriginX, Int *OriginY, Int DataType, Int Shape, Int nLevels)
{
  Int origin_x, origin_y;
  Int virtual_width, virtual_height;
  UChar *data, *indata;
  UChar *mask;
  Int wordsize = (DataType==USHORT_ENUM)?2:1;
  Int blocksize =  1 << nLevels;
  Int i, j;
  Int real_width, real_height; 
  Int max_x, max_y;
  Int min_x, min_y;
  Int rows, cols;
  UChar *a, *b, *c, *d, *f;
  
  if(blocksize%Nx!=0) blocksize = LCM(blocksize,Nx);
  if(blocksize%Ny!=0) blocksize = LCM(blocksize,Ny);

  real_width = RealWidth;
  real_height = RealHeight;
  if(Shape != VTC_RECTANGULAR) {
    /* to search for the upper left corner of the bounding box of 
       arbitrarily shaped object */
    min_x = real_width;
    min_y = real_height;
    max_x = 0;
    max_y =0;
    for(i=0,j=0;j < real_height; j++,i+=real_width){
      a=InMask+i;
      f = InMask+i+real_width;
      for(; a< f; a++){
	if(*a == Shape) {
	  min_y = j;
	  goto minx;
	}
      }
    }  
  minx:
    for(i=0;i < real_width;i++){
      a=InMask+i;
      f = InMask+i+real_width*real_height;
      for(; a< f; a+=real_width){
	if(*a == Shape) {
	  min_x = i;
	  goto maxy;
	}
      }
    }

  maxy:
    for(j=real_height-1,i= (real_height-1)*real_width;j>=0 ;j--, i-=real_width){
      a=InMask+i;
      f=InMask+i+real_width;
      for(; a <f; a++) {
	if(*a == Shape) {
	  max_y = j;
	  goto maxx;
	}
      }
    }
    
  maxx:
    for(i=real_width-1;i >= 0;i--){
      a=InMask+i;
      f = InMask+i+real_width*real_height;
      for(; a < f; a+=real_width){
	if(*a == Shape) {
	  max_x = i;
	  goto next;
	}
      }
    }
    
  next:
    /* quantize the min_x and min_y with Nx and Ny */
    if(min_x%Nx!=0) min_x=min_x/Nx*Nx;
    if(min_y%Ny!=0) min_y=min_y/Ny*Ny;
    if(min_x>max_x || min_y> max_y) {
      return(DWT_NOVALID_PIXEL); /* no valid pixel */
    }
    origin_x = min_x;
    origin_y = min_y;
    virtual_width = max_x-min_x+1;
    virtual_height = max_y-min_y+1;
   /*  fprintf(stderr, "x=%d y=%d w=%d h=%d x2=%d y2=%d\n", min_x, min_y, virtual_width, virtual_height, max_x, max_y); */
  }
  else { /* rectangular region */
    origin_x = 0; 
    origin_y = 0;
    virtual_width = RealWidth;
    virtual_height = RealHeight;
  }  
  
  /* first ajust the dimension to be multiples of blocksize */
  virtual_width =  (virtual_width+(blocksize)-1)/blocksize*blocksize;
  virtual_height =  (virtual_height+(blocksize)-1)/blocksize*blocksize;
  /* allocate proper memory and initialize */
  if ((data = (UChar *)malloc(sizeof(UChar)*virtual_width*virtual_height*wordsize)) == NULL) {
    return(DWT_MEMORY_FAILED);
  }
  memset(data, (Char )0, sizeof(UChar)*virtual_width*virtual_height*wordsize);
  if ((mask = (UChar *)malloc(sizeof(UChar)*virtual_width*virtual_height)) == NULL) {
    free(data);
    return(DWT_MEMORY_FAILED);
  }
  memset(mask, (Char )0, sizeof(UChar)*virtual_width*virtual_height);
  /* calculate clip area */
  max_y = origin_y+virtual_height;
  max_y = (max_y<real_height)?max_y:real_height;
  rows = max_y - origin_y;
  max_x = origin_x+virtual_width;
  max_x = (max_x<real_width)?max_x:real_width;
  cols = max_x - origin_x;
  indata = (UChar *)InImage;
  /* fill out data */
  for(i=0, j=origin_y*real_width+origin_x; i< rows*virtual_width;
      i+=virtual_width, j+=real_width) {
    if(Shape != VTC_RECTANGULAR) {
      f = InMask+j+cols;
      for(a= data+i*wordsize, b = indata + j*wordsize, c = InMask+j, d = mask+i;
	  c < f; c++, d++, a+=wordsize, b+=wordsize) {
	if(*c == (UChar ) Shape) {
	  memcpy(a, b, wordsize);
	  *d = IN;
	}
      }
    }
    else {
      memcpy(data+i, indata+j, wordsize*cols);
      memset(mask+i, (Char)IN, cols);
    }
  }
  *VirtualWidth = virtual_width;
  *VirtualHeight = virtual_height;
  *OriginX = origin_x;
  *OriginY = origin_y;
  *OutImage = data;
  *OutMask = mask;
  return(DWT_OK);
}

/* Function: GetMaskBox()
   Description: get the bounding box of the mask of image object
   Input:
   
   InMask -- Input image mask, can be NULL if Shape == RECTANGULAR;
   RealWidth, RealHeight  -- the size of the actual image;
   Nx, Ny -- specify  that OriginX and OriginY must be multiple of Nx and Ny
             to accomdate different color compoents configuration:
	     Examples:
	     for 420:   Nx  Ny 
	           Y:   2   2
                   U,V: 1   1
	     for 422:   
	           Y:   2   1
             for 444:
	      Y,U,V:    1   1
	     for mono:
                  Y:    1   1
	     for YUV9:  
                  Y:    4   4
                  U,V:  1   1  
  
   Shape   -- if -1, the SHAPE is rectangular, else arbitary shape and
              Shape defines the mask value of an object, useful for
	      multiple objects coding 
   nLevels -- levels of decomposition
   Output:
   
   OutMask -- Output image mask, extended area is marked as Don't-care
   VirtualWidth, VirtualHeight -- size of the output image
   OriginX, OriginY -- origins of the output image relative to the original
                       image
		       
   Return:  DWT_NOVALID_PIXEL if the mask are all zeros, otherwise DWT_OK 
            if no error;	       
   Note: The caller should free the memory OutMask allocated by this program 
         after it finishes using them.
*/

Int GetMaskBox(UChar *InMask,  UChar **OutMask, 
	       Int RealWidth, Int RealHeight, 
	       Int Nx, Int Ny,
	       Int *VirtualWidth, Int *VirtualHeight, 
	       Int *OriginX, Int *OriginY,  Int Shape, Int nLevels)
{
  Int origin_x, origin_y;
  Int virtual_width, virtual_height;
  UChar *mask;
  Int blocksize =  1 << nLevels;
  Int i, j;
  Int real_width, real_height; 
  Int max_x, max_y;
  Int min_x, min_y;
  Int rows, cols;
  UChar *a, *b, *f;
  
  if(blocksize%Nx!=0) blocksize = LCM(blocksize,Nx);
  if(blocksize%Ny!=0) blocksize = LCM(blocksize,Ny);
  
  real_width = RealWidth;
  real_height = RealHeight;
  if(Shape != VTC_RECTANGULAR) {
    /* to search for the upper left corner of the bounding box of 
       arbitrarily shaped object */
    min_x = real_width;
    min_y = real_height;
    max_x = 0;
    max_y =0;

    
    for(i=0,j=0;j < real_height; j++,i+=real_width){
      a=InMask+i;
      f = InMask+i+real_width;
      for(; a< f; a++){
	if(*a == Shape) {
	  min_y = j;
	  goto minx;
	}
      }
    }

  minx:
    for(i=0;i < real_width;i++){
      a=InMask+i;
      f=InMask+i+real_width*real_height;
      for(; a<f;  a+=real_width){
	if(*a == Shape) {
	  min_x = i;
	  goto maxy;
	}
      }
    }

  maxy:
    for(j=real_height-1,i= (real_height-1)*real_width;j>=0 ;j--, i-=real_width){
      a = InMask+i;
      f = InMask+i+real_width;;
      for(; a <f;  a++) {
	if(*a == Shape) {
	  max_y = j;
	  goto maxx;
	}
      }
    }
    
  maxx:
    for(i=real_width-1;i >= 0;i--){
      a=InMask+i;
      f =  InMask+i+real_width*real_height;
      for(; a < f; a+=real_width){
	if(*a == Shape) {
	  max_x = i;
	  goto next;
	}
      }
    }
    
  next:
    /* quantize the min_x and min_y with Nx and Ny */
    if(min_x%Nx!=0) min_x=min_x/Nx*Nx;
    if(min_y%Ny!=0) min_y=min_y/Ny*Ny;
    if(min_x>max_x || min_y> max_y) {
      return(DWT_NOVALID_PIXEL); /* no valid pixel */
    }
    origin_x = min_x;
    origin_y = min_y;
    virtual_width = max_x-min_x+1;
    virtual_height = max_y-min_y+1;
   /*  fprintf(stderr, "x=%d y=%d w=%d h=%d x2=%d y2=%d\n", min_x, min_y, virtual_width, virtual_height, max_x, max_y); */
  }
  else { /* rectangular region */
    origin_x = 0; 
    origin_y = 0;
    virtual_width = RealWidth;
    virtual_height = RealHeight;
  }  
  
  /* first ajust the dimension to be multiple of blocksize */
  virtual_width =  (virtual_width+(blocksize)-1)/blocksize*blocksize;
  virtual_height =  (virtual_height+(blocksize)-1)/blocksize*blocksize;
  if ((mask = (UChar *)malloc(sizeof(UChar)*virtual_width*virtual_height)) == NULL) {
    return(DWT_MEMORY_FAILED);
  }
  memset(mask, (Char )0, sizeof(UChar)*virtual_width*virtual_height);
  /* calculate clip area */
  max_y = origin_y+virtual_height;
  max_y = (max_y<real_height)?max_y:real_height;
  rows = max_y - origin_y;
  max_x = origin_x+virtual_width;
  max_x = (max_x<real_width)?max_x:real_width;
  cols = max_x - origin_x;
  /* fill out data */
  for(i=0, j=origin_y*real_width+origin_x; i< rows*virtual_width;
      i+=virtual_width, j+=real_width) {
    if(Shape != VTC_RECTANGULAR) {
      f = InMask+j+cols;
      for(a = InMask+j, b=mask+i; a < f; a++, b++) {
	if(*a == (UChar) Shape) *b = IN;
      }
    }
    else
      memset(mask+i, (Char )IN, cols);
  }
  *VirtualWidth = virtual_width;
  *VirtualHeight = virtual_height;
  *OriginX = origin_x;
  *OriginY = origin_y;
  *OutMask = mask;
  return(DWT_OK);
}

/* Function: ExtendMaskBox()
   Description: extend the size of bounding box of the mask of image object
                to 2^nLevels;
   Input:
   
   InMask -- Input image mask
   InWidth, InHeight  -- the size of the Input Mask;
   Nx, Ny -- specify  that OriginX and OriginY must be multiple of Nx and Ny
             to accomdate different color compoents configuration:
	     Examples:
	     for 420:   Nx  Ny 
	           Y:   2   2
                   U,V: 1   1
	     for 422:   
	           Y:   2   1
             for 444:
	      Y,U,V:    1   1
	     for mono:
                  Y:    1   1
	     for YUV9:  
                  Y:    4   4
                  U,V:  1   1     nLevels -- levels of decomposition
   Output:
   
   OutMask -- Output image mask, extended area is marked as Don't-care
   OutWidth, OutHeight -- size of the output mask
		       
   Return:  DWT_OK if no error;	       
   Note: The caller should free the memory OutMask allocated by this program 
         after it finishes using them.
*/

Int ExtendMaskBox(UChar *InMask,  UChar **OutMask, 
		  Int InWidth, Int InHeight, 
		  Int Nx, Int Ny,
		  Int *OutWidth, Int *OutHeight, 
		  Int nLevels)
{
  Int out_width, out_height;
  UChar *mask;
  Int blocksize =  1 << nLevels;
  Int i, j;
  UChar *a, *b, *f;

  if(blocksize%Nx!=0) blocksize = LCM(blocksize,Nx);
  if(blocksize%Ny!=0) blocksize = LCM(blocksize,Ny);
  
  /* first ajust the dimension to be multiple of blocksize */
  out_width =  (InWidth+(blocksize)-1)/blocksize*blocksize;
  out_height =  (InHeight+(blocksize)-1)/blocksize*blocksize;
  if ((mask = (UChar *)malloc(sizeof(UChar)*out_width*out_height)) == NULL) {
    return(DWT_MEMORY_FAILED);
  }
  memset(mask, (Char )0, sizeof(UChar)*out_width*out_height);

  /* fill out data */
  for(i=0, j=0; i< InHeight*out_width;
      i+=out_width, j+=InWidth) {
    f = InMask+j+InWidth;
    for(a = InMask+j, b=mask+i; a < f; a++, b++) {
      if(*a == (UChar) IN) *b = IN;
    }
  }
  *OutWidth = out_width;
  *OutHeight = out_height;
  *OutMask = mask;
  return(DWT_OK);
}


/* Function: PutBox()
   Description: put the bounding box of the image object back
   Input:
   
   InImage -- Input image data, data type defined by DataType;
   InMask -- Input image mask
   RealWidth, RealHeight  -- the size of the actual image;
   DataType -- 0 - unsigned char 1- unsigned short for InImage and OutImage
   Shape   -- if -1, the SHAPE is rectangular, else arbitary shape and
              Shape defines the mask value of an object, useful for
	      multiple objects coding 

   VirtualWidth, VirtualHeight -- size of the output image
   OriginX, OriginY -- origins of the output image relative to the original
                       image

   Output:
   
   OutImage -- Output image contains the bounding box image
   OutMask -- Output image mask
              NULL if Shape == RECTANGULAR;
		       
   Return:  DWT_OK if no error;	       
*/

Int PutBox(Void *InImage, UChar *InMask, Void *OutImage, UChar *OutMask, 
	   Int RealWidth, Int RealHeight, 
	   Int VirtualWidth, Int VirtualHeight, 
	   Int OriginX, Int OriginY, Int DataType, Int Shape)
{
  Int origin_x, origin_y;
  Int virtual_width, virtual_height;
  UChar *data, *indata;
  UChar *mask=NULL;
  Int wordsize = (DataType==USHORT_ENUM)?2:1;
  Int i, j;
  Int real_width, real_height; 
  Int max_x, max_y;
  Int rows, cols;
  UChar *a, *b, *c, *f;

  real_width = RealWidth;
  real_height = RealHeight;
  virtual_width = VirtualWidth;
  virtual_height = VirtualHeight;
  origin_x = OriginX;
  origin_y = OriginY;

  /* allocate proper memory and initialize to zero*/
  data = OutImage;
  memset(data, (Char )0, sizeof(UChar)*real_width*real_height*wordsize);
  if(Shape != VTC_RECTANGULAR) {
    mask = OutMask;
    memset(mask, (Char)0, sizeof(UChar)*real_width*real_height);
  }
      
  /* calculate clip area */
  max_y = origin_y+virtual_height;
  max_y = (max_y<real_height)?max_y:real_height;
  rows = max_y - origin_y;
  max_x = origin_x+virtual_width;
  max_x = (max_x<real_width)?max_x:real_width;
  cols = max_x - origin_x;
  indata = (UChar *)InImage;
  /* fill out data */
  for(i=0, j=origin_y*real_width+origin_x; i< rows*virtual_width;
      i+=virtual_width, j+=real_width) {
    f = InMask+i+cols;
    for(a = data +j*wordsize, b = indata + i*wordsize, c= InMask+i;  
	c< f; c++, a+=wordsize, b+=wordsize) {
      if(*c == IN) {
	memcpy(a, b, wordsize);
      }
    }
    if(Shape != VTC_RECTANGULAR) {
      for(a=InMask+i, b = mask+j; a<f; a++, b++) {
	if(*a == IN) *b=(UChar) Shape;
      }
    }
  }
  return(DWT_OK);
}


/* find the least common multiples of two integers */
static Int LCM(Int x, Int y)
{
  return(x*y/GCD(x,y));
}
/* find the greatest common divisor of two integers */
static Int GCD(Int x, Int y)
{
  Int i;
  Int k;
  Int d=x<y?x:y; /* the lesser of x and y */
  d = (Int) sqrt((Double)d)+1;
  k = 1;
  for(i=d;i>1;i--) {
    if(x%i==0 && y%i==0) {
      k=i;
      break;
    }
  }
  return(k);
}

/* Function: SubsampleMask()
   Description: Subsample the Mask;
   
   Input:
   InMask -- Input mask;
   Nx -- Horizontal subsampling rate;
   Ny -- vertical subsampling rate;
   Shape -- integer number specify the object in a mask;

   Output:
   OutMask -- Output mask, memory space provided by caller function;

   return: DWT_OK if no error;
*/

Void  SubsampleMask(UChar *InMask, UChar *OutMask, 
		    Int Width, Int Height,
		    Int Nx, Int Ny, Int Shape)
{
  UChar *a;
  Int width, height;
  Int i,j,k,n, p, l, m, fl, fm ;

  width = (Width + (Nx-1))/Nx*Nx;
  height = (Height+(Ny-1))/Ny*Ny;

  a = OutMask;
  memset(OutMask, (Char) 0, width/Nx*height/Ny);
  for(i=0, k=0; i< height; i+=Ny, k+=Ny*Width) {
    for(j=0; j< width; j+=Nx, a++) {
      fl = i+Ny;
      fm = j+Nx;
      for(l=i, n=k; l<fl; l++, n+=Width) {
	for(m=j, p=n+j; m<fm; m++, p++) {
	  if(l < Height && m < Width) {
	    if(InMask[p]==(UChar) Shape) *a = (UChar) Shape; 
	  }
	}
      }
    }
  }
}

