cde/programs/dtksh/ksh93/src/lib/libodelta/delta.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   6  * These libraries and programs are free software; you can
   7  * redistribute them and/or modify them under the terms of the GNU
   8  * Lesser General Public License as published by the Free Software
   9  * Foundation; either version 2 of the License, or (at your option)
  10  * any later version.
  11  *
  12  * These libraries and programs are distributed in the hope that
  13  * they will be useful, but WITHOUT ANY WARRANTY; without even the
  14  * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE. See the GNU Lesser General Public License for more
  16  * details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with these librararies and programs; if not, write
  20  * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
  21  * Floor, Boston, MA 02110-1301 USA
  22  */
  23 /* $XConsortium: delta.c /main/3 1995/11/01 19:10:54 rswiston $ */
  24 /***************************************************************
  25 *                                                              *
  26 *                      AT&T - PROPRIETARY                      *
  27 *                                                              *
  28 *         THIS IS PROPRIETARY SOURCE CODE LICENSED BY          *
  29 *                          AT&T CORP.                          *
  30 *                                                              *
  31 *                Copyright (c) 1995 AT&T Corp.                 *
  32 *                     All Rights Reserved                      *
  33 *                                                              *
  34 *           This software is licensed by AT&T Corp.            *
  35 *       under the terms and conditions of the license in       *
  36 *       http://www.research.att.com/orgs/ssr/book/reuse        *
  37 *                                                              *
  38 *               This software was created by the               *
  39 *           Software Engineering Research Department           *
  40 *                    AT&T Bell Laboratories                    *
  41 *                                                              *
  42 *               For further information contact                *
  43 *                     gsf@research.att.com                     *
  44 *                                                              *
  45 ***************************************************************/
  46
  47 /* : : generated by proto : : */
  48
  49 #if !defined(__PROTO__)
  50 #if defined(__STDC__) || defined(__cplusplus) || defined(_proto) || defined(c_plusplus)
  51 #if defined(__cplusplus)
  52 #define __MANGLE__      "C"
  53 #else
  54 #define __MANGLE__
  55 #endif
  56 #define __STDARG__
  57 #define __PROTO__(x)    x
  58 #define __OTORP__(x)
  59 #define __PARAM__(n,o)  n
  60 #if !defined(__STDC__) && !defined(__cplusplus)
  61 #if !defined(c_plusplus)
  62 #define const
  63 #endif
  64 #define signed
  65 #define void            int
  66 #define volatile
  67 #define __V_            char
  68 #else
  69 #define __V_            void
  70 #endif
  71 #else
  72 #define __PROTO__(x)    ()
  73 #define __OTORP__(x)    x
  74 #define __PARAM__(n,o)  o
  75 #define __MANGLE__
  76 #define __V_            char
  77 #define const
  78 #define signed
  79 #define void            int
  80 #define volatile
  81 #endif
  82 #if defined(__cplusplus) || defined(c_plusplus)
  83 #define __VARARG__      ...
  84 #else
  85 #define __VARARG__
  86 #endif
  87 #if defined(__STDARG__)
  88 #define __VA_START__(p,a)       va_start(p,a)
  89 #else
  90 #define __VA_START__(p,a)       va_start(p)
  91 #endif
  92 #endif
  93 #include        "update.h"
  94 #include        "suftree.h"
  95
  96 /*
  97 **      Compute delta commands to transform the source string 'src'
  98 **      to the target string 'tar'. Small blockmoves are transformed
  99 **      to blockadds for space efficiency.
 100 **      Return -1 in case of error.
 101 **
 102 **      For details on computing blockmoves, see:
 103 **      "The String-to-String Correction Problem with Block Moves"
 104 **      W. Tichy, ACM TOCS, v.2, No.4, 1984, pp.309-321.
 105 **
 106 **      Written by Kiem-Phong Vo, 5/18/88
 107 */
 108
 109 #define M_MAX   9       /* max size of a block move instruction */
 110 #define A_MAX   5       /* max size of the header of an add instruction */
 111
 112 /* structure of a delta instruction */
 113 typedef struct _m_
 114 {
 115         int             type;   /* DELTA_MOVE or DELTA_ADD */
 116         long            size;   /* size of the block being moved or added */
 117         long            addr;   /* offset where the block starts */
 118         struct _m_      *last;  /* doubly linked list for easy insert/delete */
 119         struct _m_      *next;
 120 } Move;
 121
 122 /* bases of the source and target strings */
 123 static char     *Bsrc, *Btar;
 124
 125 /* Data buffer area */
 126 static char     *Ddata, *Dend, *Dnext;
 127 static int      Dfd;
 128
 129 #define delinit(buf,fd) (Ddata=Dnext=buf, Dend=buf+BUFSIZE, Dfd=fd)
 130 #define delflush()      (write(Dfd,Ddata,Dnext-Ddata) >= 0 ? (Dnext=Ddata,0) : -1)
 131
 132 static int delputc __PARAM__((int byte), (byte)) __OTORP__(int byte;){
 133         if(Dnext == Dend)
 134                 if(delflush() < 0)
 135                         return -1;
 136         *Dnext++ = byte;
 137         return 0;
 138 }
 139
 140 static int delputl __PARAM__((register int n, register long v), (n, v)) __OTORP__(register int n; register long v;){
 141         register int    i;
 142         unsigned char   c[4];
 143
 144         for(i = 0; i < n; ++i)
 145         {
 146                 c[i] = (unsigned char)(v%BASE);
 147                 v /= BASE;
 148         }
 149         for(i = n-1; i >= 0; --i)
 150                 if(delputc((char)c[i]) < 0)
 151                         return -1;
 152         return 0;
 153 }
 154
 155 static int delputs __PARAM__((register long n, register long addr), (n, addr)) __OTORP__(register long n; register long addr;){
 156         if(n < (Dend-Dnext))
 157         {
 158                 memcpy(Dnext,Btar+addr,n);
 159                 Dnext += n;
 160         }
 161         else
 162         {
 163                 if(delflush() < 0)
 164                         return -1;
 165                 if(write(Dfd,Btar+addr,n) != n)
 166                         return -1;
 167         }
 168         return 0;
 169 }
 170
 171 /* write an instruction */
 172 static int putMove __PARAM__((Move* ip), (ip)) __OTORP__(Move* ip;){
 173         register char   inst;
 174
 175         inst = ip->type;
 176         inst |= (NBYTE(ip->size)&07) << 3;
 177         if(ip->type == DELTA_MOVE)
 178         {
 179                 inst |= NBYTE(ip->addr)&07;
 180                 if(delputc(inst) < 0 ||
 181                    delputl(NBYTE(ip->size),ip->size) < 0 ||
 182                    delputl(NBYTE(ip->addr),ip->addr) < 0)
 183                         return -1;
 184         }
 185         else
 186         {
 187                 if(delputc(inst) < 0 ||
 188                    delputl(NBYTE(ip->size),ip->size) < 0 ||
 189                    delputs(ip->size,ip->addr) < 0)
 190                         return -1;
 191         }
 192         return 0;
 193 }
 194
 195 /* constructor for Move */
 196 static Move *newMove __PARAM__((int type, long size, long addr, Move* last), (type, size, addr, last)) __OTORP__(int type; long size; long addr; Move* last;){
 197         register Move *ip = (Move*) malloc(sizeof(Move));
 198         if(!ip) return 0;
 199         ip->type = type;
 200         ip->size = size;
 201         ip->addr = addr;
 202         if(last)
 203         {
 204                 last->next = ip;
 205                 ip->last = last;
 206         }
 207         else    ip->last = 0;
 208         ip->next = 0;
 209         return ip;
 210 }
 211
 212 /* destructor for Move, return the elt after move */
 213 static Move *delMove __PARAM__((Move* ip), (ip)) __OTORP__(Move* ip;){
 214         register Move *next = ip->next;
 215         register Move *last = ip->last;
 216         if(last)
 217                 last->next = next;
 218         if(next)
 219                 next->last = last;
 220         free(ip);
 221         return next ? next : last;
 222 }
 223
 224 /* make a new add command */
 225 static Move *makeAdd __PARAM__((char* beg, char* end, Move* last), (beg, end, last)) __OTORP__(char* beg; char* end; Move* last;){
 226         register Move   *ip;
 227
 228         ip = newMove(DELTA_ADD,(long)(end-beg),(long)(beg-Btar),NiL);
 229         if(!ip)
 230                 return 0;
 231
 232         /* remove small previous adjacent moves */
 233         while(last)
 234         {
 235                 register int a_size, cost_m, cost_a;
 236
 237                 if(last->type == DELTA_ADD)
 238                         break;
 239
 240                 cost_m = NBYTE(last->size) + NBYTE(last->addr) +
 241                          NBYTE(ip->size) + ip->size;
 242                 a_size = ip->size + last->size;
 243                 cost_a = NBYTE(a_size) + a_size;
 244                 if(cost_m < cost_a)
 245                         break;
 246
 247                 ip->size  = a_size;
 248                 ip->addr -= last->size;
 249                 last = delMove(last);
 250         }
 251
 252         /* merge with adjacent adds */
 253         if(last && last->type == DELTA_ADD)
 254         {
 255                 ip->size += last->size;
 256                 ip->addr -= last->size;
 257                 last = delMove(last);
 258         }
 259
 260         if(last)
 261         {
 262                 last->next = ip;
 263                 ip->last = last;
 264         }
 265         return ip;
 266 }
 267
 268 /* check to see if a move is appropriate */
 269 static int chkMove __PARAM__((long m_size, long m_addr, long a_size), (m_size, m_addr, a_size)) __OTORP__(long m_size; long m_addr; long a_size;){
 270         register int cost_m, cost_a;
 271
 272         cost_m = NBYTE(m_size) + NBYTE(m_addr);
 273         cost_a = NBYTE(m_size) + m_size;
 274         if(cost_m >= cost_a)
 275                 return 0;
 276
 277         /* it's good but it may be better to merge it to an add */
 278         if(a_size > 0)
 279         {
 280                 register int m_cost, a_cost;
 281
 282                 m_cost = cost_m + NBYTE(a_size) + a_size;
 283                 a_size += m_size;
 284                 a_cost = NBYTE(a_size) + a_size;
 285
 286                 /* it is better to merge! */
 287                 if(m_cost >= a_cost)
 288                         return 0;
 289         }
 290
 291         return m_size;
 292 }
 293
 294 /* optimize a sequence of moves */
 295 static Move *optMove __PARAM__((register Move* s), (s)) __OTORP__(register Move* s;){
 296         register long   add, m_cost, a_cost;
 297         register Move   *ip, *last;
 298
 299         add = (s->last && s->last->type == DELTA_ADD) ? s->last->size : 0;
 300
 301         m_cost = 0;
 302         a_cost = 0;
 303         for(ip = s; ip; ip = ip->next)
 304         {
 305                 register long cost_m, cost_a;
 306
 307                 if(ip->type == DELTA_ADD || ip->size > (M_MAX+A_MAX))
 308                         break;
 309
 310                 m_cost += 1+NBYTE(ip->size)+NBYTE(ip->addr);
 311                 a_cost += ip->size;
 312
 313                 /* costs of alternatives */
 314                 cost_m = m_cost;
 315                 cost_a = a_cost;
 316                 if(add > 0)
 317                 {
 318                         cost_m += 1 + add + NBYTE(add);
 319                         cost_a += add;
 320                 }
 321                 if(ip->next && ip->next->type == DELTA_ADD)
 322                 {
 323                         cost_m += 1 + ip->next->size + NBYTE(ip->next->size);
 324                         cost_a += ip->next->size;
 325                 }
 326                 cost_a += 1 + NBYTE(cost_a);
 327
 328                 /* conversion is bad */
 329                 if(cost_m < cost_a)
 330                         continue;
 331
 332                 /* convert the entire sequence to an add */
 333                 s->type = DELTA_ADD;
 334                 while(ip != s)
 335                 {
 336                         last = ip->last;
 337                         s->size += ip->size;
 338                         delMove(ip);
 339                         ip = last;
 340                 }
 341
 342                 /* merge adjacent adds */
 343                 if((last = s->last) && last->type == DELTA_ADD)
 344                 {
 345                         last->size += s->size;
 346                         delMove(s);
 347                         s = last;
 348                 }
 349                 if(s->next && s->next->type == DELTA_ADD)
 350                 {
 351                         s->size += s->next->size;
 352                         delMove(s->next);
 353                 }
 354                 /* done */
 355                 break;
 356         }
 357         return s;
 358 }
 359
 360 /* the real thing */
 361 int
 362 delta __PARAM__((char* src, long n_src, char* tar, long n_tar, int delfd), (src, n_src, tar, n_tar, delfd)) __OTORP__(char* src; long n_src; char* tar; long n_tar; int delfd;){
 363         register char   *sp, *tp, *esrc, *etar;
 364         register long   size, addr;
 365         Suftree         *tree;
 366         Move            *moves, *last;
 367         char            inst, buf[BUFSIZE];
 368
 369         /* initialize the output area */
 370         delinit(buf,delfd);
 371
 372         /* output file sizes */
 373         inst = DELTA_TYPE | ((NBYTE(n_src)&07) << 3) | (NBYTE(n_tar)&07);
 374         if(delputc(inst) < 0)
 375                 return -1;
 376         if(delputl(NBYTE(n_src),n_src) < 0 || delputl(NBYTE(n_tar),n_tar) < 0)
 377                 return -1;
 378
 379         /* bases */
 380         Bsrc = src;
 381         Btar = tar;
 382         esrc = src + n_src - 1;
 383         etar = tar + n_tar - 1;
 384
 385         /* initialize list and last block */
 386         moves = 0;
 387         last = 0;
 388
 389         /* try making suffix tree */
 390         if(!(tree = n_tar > 0 ? bldsuftree(src,n_src) : (Suftree*)0))
 391         {
 392                 /* not enough space for tree, remove matching prefix and suffix */
 393                 for(; src <= esrc && tar <= etar; ++src, ++tar)
 394                         if(*src != *tar)
 395                                 break;
 396                 if((size = src-Bsrc) > 0)
 397                 {
 398                         register int cost_m, cost_a;
 399
 400                         cost_m = NBYTE(size) + NBYTE(0);
 401                         cost_a = NBYTE(size) + size;
 402                         if(cost_m < cost_a)
 403                         {
 404                                 moves = newMove(DELTA_MOVE,size,0L,NiL);
 405                                 if(!moves)
 406                                         return -1;
 407                                 n_src -= src-Bsrc;
 408                                 n_tar -= tar-Btar;
 409                         }
 410                         else
 411                         {
 412                                 src = Bsrc;
 413                                 tar = Btar;
 414                         }
 415                 }
 416
 417                 for(sp = esrc, tp = etar; sp >= src && tp >= tar; --sp, --tp)
 418                         if(*sp != *tp)
 419                                 break;
 420                 if((size = esrc-sp) > 0)
 421                 {
 422                         addr = sp+1-Bsrc;
 423                         if(chkMove(size,addr,0L) > 0)
 424                         {
 425                                 last = newMove(DELTA_MOVE,size,addr,NiL);
 426                                 if(!last)
 427                                         return -1;
 428                                 esrc = sp;
 429                                 etar = tp;
 430                                 n_tar = etar-tar+1;
 431                                 n_src = esrc-src+1;
 432                         }
 433                 }
 434
 435                 /* try making the tree again */
 436                 tree = n_tar > 0 ? bldsuftree(src,n_src) : (Suftree*)0;
 437         }
 438
 439         /* compute block moves */
 440         tp = 0;
 441         while(n_tar > 0)
 442         {
 443                 char    *match;
 444
 445                 if(tree)
 446                         size = mtchsuftree(tree,tar,n_tar,&match);
 447                 else    size = mtchstring(src,n_src,tar,n_tar,&match);
 448                 if(size < 0)
 449                         return -1;
 450                 if(size > 0)
 451                         size = chkMove(size,(long)(match-Bsrc),(long)(tp ? tp-tar : 0));
 452
 453                 /* output a block move */
 454                 if(size > 0)
 455                 {
 456                         if(tp)
 457                         {
 458                                 moves = makeAdd(tp,tar,moves);
 459                                 if(!moves)
 460                                         return -1;
 461                                 tp = 0;
 462                         }
 463                         moves = newMove(DELTA_MOVE,size,(long)(match-Bsrc),moves);
 464                         if(!moves)
 465                                 return -1;
 466                         tar += size;
 467                         n_tar -= size;
 468                 }
 469                 else
 470                 {
 471                         if(!tp)
 472                                 tp = tar;
 473                         tar += 1;
 474                         n_tar -= 1;
 475                 }
 476         }
 477
 478         /* add any remaining blocks */
 479         if(tp)
 480         {
 481                 if(last && chkMove(last->size,last->addr,(long)(tar-tp)) <= 0)
 482                 {
 483                         tar += last->size;
 484                         last = delMove(last);
 485                 }
 486                 moves = makeAdd(tp,tar,moves);
 487                 if(!moves)
 488                         return -1;
 489         }
 490         if(last)
 491         {
 492                 moves->next = last;
 493                 last->last = moves;
 494         }
 495
 496         /* release space use for string matching */
 497         if(tree)
 498                 delsuftree(tree);
 499         else    mtchstring(NiL,0L,NiL,0L,NiL);
 500
 501         /* optimize move instructions */
 502         if(moves)
 503         {
 504                 register Move   *ip;
 505
 506                 ip = moves;
 507                 while(ip->last)
 508                         ip = ip->last;
 509                 for(; ip; ip = ip->next)
 510                         if(ip->type == DELTA_MOVE && ip->size <= (M_MAX+A_MAX))
 511                                 moves = ip = optMove(ip);
 512
 513                 while(moves->last)
 514                         moves = moves->last;
 515         }
 516
 517         /* write out the move instructions */
 518         addr = 0L;
 519         while(moves)
 520         {
 521                 if(moves->type == DELTA_ADD)
 522                         moves->addr = addr;
 523                 addr += moves->size;
 524                 if(putMove(moves) < 0)
 525                         return -1;
 526                 moves = delMove(moves);
 527         }
 528
 529         /* write ending token */
 530         delputc((char)DELTA_TYPE);
 531
 532         /* flush buffer */
 533         return delflush();
 534 }