sbin/fsck_msdosfs/fat.c

   1 /*
   2  * Copyright (C) 1995, 1996, 1997 Wolfgang Solfrank
   3  * Copyright (c) 1995 Martin Husemann
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by Martin Husemann
  16  *      and Wolfgang Solfrank.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHORS ``AS IS'' AND ANY EXPRESS OR
  22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  23  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  24  * IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  26  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  30  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32
  33
  34 #include <sys/cdefs.h>
  35 #ifndef lint
  36 __RCSID("$NetBSD: fat.c,v 1.12 2000/10/10 20:24:52 is Exp $");
  37 static const char rcsid[] =
  38   "$FreeBSD$";
  39 #endif /* not lint */
  40
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <ctype.h>
  44 #include <stdio.h>
  45 #include <unistd.h>
  46
  47 #include "ext.h"
  48 #include "fsutil.h"
  49
  50 static int checkclnum(struct bootblock *, int, cl_t, cl_t *);
  51 static int clustdiffer(cl_t, cl_t *, cl_t *, int);
  52 static int tryclear(struct bootblock *, struct fatEntry *, cl_t, cl_t *);
  53 static int _readfat(int, struct bootblock *, int, u_char **);
  54
  55 /*
  56  * Check a cluster number for valid value
  57  */
  58 static int
  59 checkclnum(struct bootblock *boot, int fat, cl_t cl, cl_t *next)
  60 {
  61         if (*next >= (CLUST_RSRVD&boot->ClustMask))
  62                 *next |= ~boot->ClustMask;
  63         if (*next == CLUST_FREE) {
  64                 boot->NumFree++;
  65                 return FSOK;
  66         }
  67         if (*next == CLUST_BAD) {
  68                 boot->NumBad++;
  69                 return FSOK;
  70         }
  71         if (*next < CLUST_FIRST
  72             || (*next >= boot->NumClusters && *next < CLUST_EOFS)) {
  73                 pwarn("Cluster %u in FAT %d continues with %s cluster number %u\n",
  74                       cl, fat,
  75                       *next < CLUST_RSRVD ? "out of range" : "reserved",
  76                       *next&boot->ClustMask);
  77                 if (ask(0, "Truncate")) {
  78                         *next = CLUST_EOF;
  79                         return FSFATMOD;
  80                 }
  81                 return FSERROR;
  82         }
  83         return FSOK;
  84 }
  85
  86 /*
  87  * Read a FAT from disk. Returns 1 if successful, 0 otherwise.
  88  */
  89 static int
  90 _readfat(int fs, struct bootblock *boot, int no, u_char **buffer)
  91 {
  92         off_t off;
  93
  94         *buffer = malloc(boot->FATsecs * boot->BytesPerSec);
  95         if (*buffer == NULL) {
  96                 perror("No space for FAT");
  97                 return 0;
  98         }
  99
 100         off = boot->ResSectors + no * boot->FATsecs;
 101         off *= boot->BytesPerSec;
 102
 103         if (lseek(fs, off, SEEK_SET) != off) {
 104                 perror("Unable to read FAT");
 105                 goto err;
 106         }
 107
 108         if (read(fs, *buffer, boot->FATsecs * boot->BytesPerSec)
 109             != boot->FATsecs * boot->BytesPerSec) {
 110                 perror("Unable to read FAT");
 111                 goto err;
 112         }
 113
 114         return 1;
 115
 116     err:
 117         free(*buffer);
 118         return 0;
 119 }
 120
 121 /*
 122  * Read a FAT and decode it into internal format
 123  */
 124 int
 125 readfat(int fs, struct bootblock *boot, int no, struct fatEntry **fp)
 126 {
 127         struct fatEntry *fat;
 128         u_char *buffer, *p;
 129         cl_t cl;
 130         int ret = FSOK;
 131
 132         boot->NumFree = boot->NumBad = 0;
 133
 134         if (!_readfat(fs, boot, no, &buffer))
 135                 return FSFATAL;
 136
 137         fat = calloc(boot->NumClusters, sizeof(struct fatEntry));
 138         if (fat == NULL) {
 139                 perror("No space for FAT");
 140                 free(buffer);
 141                 return FSFATAL;
 142         }
 143
 144         if (buffer[0] != boot->Media
 145             || buffer[1] != 0xff || buffer[2] != 0xff
 146             || (boot->ClustMask == CLUST16_MASK && buffer[3] != 0xff)
 147             || (boot->ClustMask == CLUST32_MASK
 148                 && ((buffer[3]&0x0f) != 0x0f
 149                     || buffer[4] != 0xff || buffer[5] != 0xff
 150                     || buffer[6] != 0xff || (buffer[7]&0x0f) != 0x0f))) {
 151
 152                 /* Windows 95 OSR2 (and possibly any later) changes
 153                  * the FAT signature to 0xXXffff7f for FAT16 and to
 154                  * 0xXXffff0fffffff07 for FAT32 upon boot, to know that the
 155                  * filesystem is dirty if it doesn't reboot cleanly.
 156                  * Check this special condition before errorring out.
 157                  */
 158                 if (buffer[0] == boot->Media && buffer[1] == 0xff
 159                     && buffer[2] == 0xff
 160                     && ((boot->ClustMask == CLUST16_MASK && buffer[3] == 0x7f)
 161                         || (boot->ClustMask == CLUST32_MASK
 162                             && buffer[3] == 0x0f && buffer[4] == 0xff
 163                             && buffer[5] == 0xff && buffer[6] == 0xff
 164                             && buffer[7] == 0x07)))
 165                         ret |= FSDIRTY;
 166                 else {
 167                         /* just some odd byte sequence in FAT */
 168
 169                         switch (boot->ClustMask) {
 170                         case CLUST32_MASK:
 171                                 pwarn("%s (%02x%02x%02x%02x%02x%02x%02x%02x)\n",
 172                                       "FAT starts with odd byte sequence",
 173                                       buffer[0], buffer[1], buffer[2], buffer[3],
 174                                       buffer[4], buffer[5], buffer[6], buffer[7]);
 175                                 break;
 176                         case CLUST16_MASK:
 177                                 pwarn("%s (%02x%02x%02x%02x)\n",
 178                                     "FAT starts with odd byte sequence",
 179                                     buffer[0], buffer[1], buffer[2], buffer[3]);
 180                                 break;
 181                         default:
 182                                 pwarn("%s (%02x%02x%02x)\n",
 183                                     "FAT starts with odd byte sequence",
 184                                     buffer[0], buffer[1], buffer[2]);
 185                                 break;
 186                         }
 187
 188
 189                         if (ask(1, "Correct"))
 190                                 ret |= FSFIXFAT;
 191                 }
 192         }
 193         switch (boot->ClustMask) {
 194         case CLUST32_MASK:
 195                 p = buffer + 8;
 196                 break;
 197         case CLUST16_MASK:
 198                 p = buffer + 4;
 199                 break;
 200         default:
 201                 p = buffer + 3;
 202                 break;
 203         }
 204         for (cl = CLUST_FIRST; cl < boot->NumClusters;) {
 205                 switch (boot->ClustMask) {
 206                 case CLUST32_MASK:
 207                         fat[cl].next = p[0] + (p[1] << 8)
 208                                        + (p[2] << 16) + (p[3] << 24);
 209                         fat[cl].next &= boot->ClustMask;
 210                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
 211                         cl++;
 212                         p += 4;
 213                         break;
 214                 case CLUST16_MASK:
 215                         fat[cl].next = p[0] + (p[1] << 8);
 216                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
 217                         cl++;
 218                         p += 2;
 219                         break;
 220                 default:
 221                         fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;
 222                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
 223                         cl++;
 224                         if (cl >= boot->NumClusters)
 225                                 break;
 226                         fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;
 227                         ret |= checkclnum(boot, no, cl, &fat[cl].next);
 228                         cl++;
 229                         p += 3;
 230                         break;
 231                 }
 232         }
 233
 234         free(buffer);
 235         *fp = fat;
 236         return ret;
 237 }
 238
 239 /*
 240  * Get type of reserved cluster
 241  */
 242 char *
 243 rsrvdcltype(cl_t cl)
 244 {
 245         if (cl == CLUST_FREE)
 246                 return "free";
 247         if (cl < CLUST_BAD)
 248                 return "reserved";
 249         if (cl > CLUST_BAD)
 250                 return "as EOF";
 251         return "bad";
 252 }
 253
 254 static int
 255 clustdiffer(cl_t cl, cl_t *cp1, cl_t *cp2, int fatnum)
 256 {
 257         if (*cp1 == CLUST_FREE || *cp1 >= CLUST_RSRVD) {
 258                 if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
 259                         if ((*cp1 != CLUST_FREE && *cp1 < CLUST_BAD
 260                              && *cp2 != CLUST_FREE && *cp2 < CLUST_BAD)
 261                             || (*cp1 > CLUST_BAD && *cp2 > CLUST_BAD)) {
 262                                 pwarn("Cluster %u is marked %s with different indicators, ",
 263                                       cl, rsrvdcltype(*cp1));
 264                                 if (ask(1, "fix")) {
 265                                         *cp2 = *cp1;
 266                                         return FSFATMOD;
 267                                 }
 268                                 return FSFATAL;
 269                         }
 270                         pwarn("Cluster %u is marked %s in FAT 0, %s in FAT %d\n",
 271                               cl, rsrvdcltype(*cp1), rsrvdcltype(*cp2), fatnum);
 272                         if (ask(0, "use FAT 0's entry")) {
 273                                 *cp2 = *cp1;
 274                                 return FSFATMOD;
 275                         }
 276                         if (ask(0, "use FAT %d's entry", fatnum)) {
 277                                 *cp1 = *cp2;
 278                                 return FSFATMOD;
 279                         }
 280                         return FSFATAL;
 281                 }
 282                 pwarn("Cluster %u is marked %s in FAT 0, but continues with cluster %u in FAT %d\n",
 283                       cl, rsrvdcltype(*cp1), *cp2, fatnum);
 284                 if (ask(0, "Use continuation from FAT %d", fatnum)) {
 285                         *cp1 = *cp2;
 286                         return FSFATMOD;
 287                 }
 288                 if (ask(0, "Use mark from FAT 0")) {
 289                         *cp2 = *cp1;
 290                         return FSFATMOD;
 291                 }
 292                 return FSFATAL;
 293         }
 294         if (*cp2 == CLUST_FREE || *cp2 >= CLUST_RSRVD) {
 295                 pwarn("Cluster %u continues with cluster %u in FAT 0, but is marked %s in FAT %d\n",
 296                       cl, *cp1, rsrvdcltype(*cp2), fatnum);
 297                 if (ask(0, "Use continuation from FAT 0")) {
 298                         *cp2 = *cp1;
 299                         return FSFATMOD;
 300                 }
 301                 if (ask(0, "Use mark from FAT %d", fatnum)) {
 302                         *cp1 = *cp2;
 303                         return FSFATMOD;
 304                 }
 305                 return FSERROR;
 306         }
 307         pwarn("Cluster %u continues with cluster %u in FAT 0, but with cluster %u in FAT %d\n",
 308               cl, *cp1, *cp2, fatnum);
 309         if (ask(0, "Use continuation from FAT 0")) {
 310                 *cp2 = *cp1;
 311                 return FSFATMOD;
 312         }
 313         if (ask(0, "Use continuation from FAT %d", fatnum)) {
 314                 *cp1 = *cp2;
 315                 return FSFATMOD;
 316         }
 317         return FSERROR;
 318 }
 319
 320 /*
 321  * Compare two FAT copies in memory. Resolve any conflicts and merge them
 322  * into the first one.
 323  */
 324 int
 325 comparefat(struct bootblock *boot, struct fatEntry *first,
 326     struct fatEntry *second, int fatnum)
 327 {
 328         cl_t cl;
 329         int ret = FSOK;
 330
 331         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++)
 332                 if (first[cl].next != second[cl].next)
 333                         ret |= clustdiffer(cl, &first[cl].next, &second[cl].next, fatnum);
 334         return ret;
 335 }
 336
 337 void
 338 clearchain(struct bootblock *boot, struct fatEntry *fat, cl_t head)
 339 {
 340         cl_t p, q;
 341
 342         for (p = head; p >= CLUST_FIRST && p < boot->NumClusters; p = q) {
 343                 if (fat[p].head != head)
 344                         break;
 345                 q = fat[p].next;
 346                 fat[p].next = fat[p].head = CLUST_FREE;
 347                 fat[p].length = 0;
 348         }
 349 }
 350
 351 int
 352 tryclear(struct bootblock *boot, struct fatEntry *fat, cl_t head, cl_t *trunc)
 353 {
 354         if (ask(0, "Clear chain starting at %u", head)) {
 355                 clearchain(boot, fat, head);
 356                 return FSFATMOD;
 357         } else if (ask(0, "Truncate")) {
 358                 *trunc = CLUST_EOF;
 359                 return FSFATMOD;
 360         } else
 361                 return FSERROR;
 362 }
 363
 364 /*
 365  * Check a complete FAT in-memory for crosslinks
 366  */
 367 int
 368 checkfat(struct bootblock *boot, struct fatEntry *fat)
 369 {
 370         cl_t head, p, h, n;
 371         u_int len;
 372         int ret = 0;
 373         int conf;
 374
 375         /*
 376          * pass 1: figure out the cluster chains.
 377          */
 378         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
 379                 /* find next untravelled chain */
 380                 if (fat[head].head != 0         /* cluster already belongs to some chain */
 381                     || fat[head].next == CLUST_FREE
 382                     || fat[head].next == CLUST_BAD)
 383                         continue;               /* skip it. */
 384
 385                 /* follow the chain and mark all clusters on the way */
 386                 for (len = 0, p = head;
 387                      p >= CLUST_FIRST && p < boot->NumClusters;
 388                      p = fat[p].next) {
 389                         fat[p].head = head;
 390                         len++;
 391                 }
 392
 393                 /* the head record gets the length */
 394                 fat[head].length = fat[head].next == CLUST_FREE ? 0 : len;
 395         }
 396
 397         /*
 398          * pass 2: check for crosslinked chains (we couldn't do this in pass 1 because
 399          * we didn't know the real start of the chain then - would have treated partial
 400          * chains as interlinked with their main chain)
 401          */
 402         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
 403                 /* find next untravelled chain */
 404                 if (fat[head].head != head)
 405                         continue;
 406
 407                 /* follow the chain to its end (hopefully) */
 408                 for (p = head;
 409                      (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters;
 410                      p = n)
 411                         if (fat[n].head != head)
 412                                 break;
 413                 if (n >= CLUST_EOFS)
 414                         continue;
 415
 416                 if (n == CLUST_FREE || n >= CLUST_RSRVD) {
 417                         pwarn("Cluster chain starting at %u ends with cluster marked %s\n",
 418                               head, rsrvdcltype(n));
 419                         ret |= tryclear(boot, fat, head, &fat[p].next);
 420                         continue;
 421                 }
 422                 if (n < CLUST_FIRST || n >= boot->NumClusters) {
 423                         pwarn("Cluster chain starting at %u ends with cluster out of range (%u)\n",
 424                               head, n);
 425                         ret |= tryclear(boot, fat, head, &fat[p].next);
 426                         continue;
 427                 }
 428                 pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",
 429                       head, fat[n].head, n);
 430                 conf = tryclear(boot, fat, head, &fat[p].next);
 431                 if (ask(0, "Clear chain starting at %u", h = fat[n].head)) {
 432                         if (conf == FSERROR) {
 433                                 /*
 434                                  * Transfer the common chain to the one not cleared above.
 435                                  */
 436                                 for (p = n;
 437                                      p >= CLUST_FIRST && p < boot->NumClusters;
 438                                      p = fat[p].next) {
 439                                         if (h != fat[p].head) {
 440                                                 /*
 441                                                  * Have to reexamine this chain.
 442                                                  */
 443                                                 head--;
 444                                                 break;
 445                                         }
 446                                         fat[p].head = head;
 447                                 }
 448                         }
 449                         clearchain(boot, fat, h);
 450                         conf |= FSFATMOD;
 451                 }
 452                 ret |= conf;
 453         }
 454
 455         return ret;
 456 }
 457
 458 /*
 459  * Write out FATs encoding them from the internal format
 460  */
 461 int
 462 writefat(int fs, struct bootblock *boot, struct fatEntry *fat, int correct_fat)
 463 {
 464         u_char *buffer, *p;
 465         cl_t cl;
 466         int i;
 467         u_int32_t fatsz;
 468         off_t off;
 469         int ret = FSOK;
 470
 471         buffer = malloc(fatsz = boot->FATsecs * boot->BytesPerSec);
 472         if (buffer == NULL) {
 473                 perror("No space for FAT");
 474                 return FSFATAL;
 475         }
 476         memset(buffer, 0, fatsz);
 477         boot->NumFree = 0;
 478         p = buffer;
 479         if (correct_fat) {
 480                 *p++ = (u_char)boot->Media;
 481                 *p++ = 0xff;
 482                 *p++ = 0xff;
 483                 switch (boot->ClustMask) {
 484                 case CLUST16_MASK:
 485                         *p++ = 0xff;
 486                         break;
 487                 case CLUST32_MASK:
 488                         *p++ = 0x0f;
 489                         *p++ = 0xff;
 490                         *p++ = 0xff;
 491                         *p++ = 0xff;
 492                         *p++ = 0x0f;
 493                         break;
 494                 }
 495         } else {
 496                 /* use same FAT signature as the old FAT has */
 497                 int count;
 498                 u_char *old_fat;
 499
 500                 switch (boot->ClustMask) {
 501                 case CLUST32_MASK:
 502                         count = 8;
 503                         break;
 504                 case CLUST16_MASK:
 505                         count = 4;
 506                         break;
 507                 default:
 508                         count = 3;
 509                         break;
 510                 }
 511
 512                 if (!_readfat(fs, boot, boot->ValidFat >= 0 ? boot->ValidFat :0,
 513                                          &old_fat)) {
 514                         free(buffer);
 515                         return FSFATAL;
 516                 }
 517
 518                 memcpy(p, old_fat, count);
 519                 free(old_fat);
 520                 p += count;
 521         }
 522
 523         for (cl = CLUST_FIRST; cl < boot->NumClusters; cl++) {
 524                 switch (boot->ClustMask) {
 525                 case CLUST32_MASK:
 526                         if (fat[cl].next == CLUST_FREE)
 527                                 boot->NumFree++;
 528                         *p++ = (u_char)fat[cl].next;
 529                         *p++ = (u_char)(fat[cl].next >> 8);
 530                         *p++ = (u_char)(fat[cl].next >> 16);
 531                         *p &= 0xf0;
 532                         *p++ |= (fat[cl].next >> 24)&0x0f;
 533                         break;
 534                 case CLUST16_MASK:
 535                         if (fat[cl].next == CLUST_FREE)
 536                                 boot->NumFree++;
 537                         *p++ = (u_char)fat[cl].next;
 538                         *p++ = (u_char)(fat[cl].next >> 8);
 539                         break;
 540                 default:
 541                         if (fat[cl].next == CLUST_FREE)
 542                                 boot->NumFree++;
 543                         if (cl + 1 < boot->NumClusters
 544                             && fat[cl + 1].next == CLUST_FREE)
 545                                 boot->NumFree++;
 546                         *p++ = (u_char)fat[cl].next;
 547                         *p++ = (u_char)((fat[cl].next >> 8) & 0xf)
 548                                |(u_char)(fat[cl+1].next << 4);
 549                         *p++ = (u_char)(fat[++cl].next >> 4);
 550                         break;
 551                 }
 552         }
 553         for (i = 0; i < boot->FATs; i++) {
 554                 off = boot->ResSectors + i * boot->FATsecs;
 555                 off *= boot->BytesPerSec;
 556                 if (lseek(fs, off, SEEK_SET) != off
 557                     || write(fs, buffer, fatsz) != fatsz) {
 558                         perror("Unable to write FAT");
 559                         ret = FSFATAL; /* Return immediately?           XXX */
 560                 }
 561         }
 562         free(buffer);
 563         return ret;
 564 }
 565
 566 /*
 567  * Check a complete in-memory FAT for lost cluster chains
 568  */
 569 int
 570 checklost(int dosfs, struct bootblock *boot, struct fatEntry *fat)
 571 {
 572         cl_t head;
 573         int mod = FSOK;
 574         int ret;
 575
 576         for (head = CLUST_FIRST; head < boot->NumClusters; head++) {
 577                 /* find next untravelled chain */
 578                 if (fat[head].head != head
 579                     || fat[head].next == CLUST_FREE
 580                     || (fat[head].next >= CLUST_RSRVD
 581                         && fat[head].next < CLUST_EOFS)
 582                     || (fat[head].flags & FAT_USED))
 583                         continue;
 584
 585                 pwarn("Lost cluster chain at cluster %u\n%d Cluster(s) lost\n",
 586                       head, fat[head].length);
 587                 mod |= ret = reconnect(dosfs, boot, fat, head);
 588                 if (mod & FSFATAL)
 589                         break;
 590                 if (ret == FSERROR && ask(0, "Clear")) {
 591                         clearchain(boot, fat, head);
 592                         mod |= FSFATMOD;
 593                 }
 594         }
 595         finishlf();
 596
 597         if (boot->FSInfo) {
 598                 ret = 0;
 599                 if (boot->FSFree != boot->NumFree) {
 600                         pwarn("Free space in FSInfo block (%d) not correct (%d)\n",
 601                               boot->FSFree, boot->NumFree);
 602                         if (ask(1, "fix")) {
 603                                 boot->FSFree = boot->NumFree;
 604                                 ret = 1;
 605                         }
 606                 }
 607                 if (boot->NumFree && fat[boot->FSNext].next != CLUST_FREE) {
 608                         pwarn("Next free cluster in FSInfo block (%u) not free\n",
 609                               boot->FSNext);
 610                         if (ask(1, "fix"))
 611                                 for (head = CLUST_FIRST; head < boot->NumClusters; head++)
 612                                         if (fat[head].next == CLUST_FREE) {
 613                                                 boot->FSNext = head;
 614                                                 ret = 1;
 615                                                 break;
 616                                         }
 617                 }
 618                 if (ret)
 619                         mod |= writefsinfo(dosfs, boot);
 620         }
 621
 622         return mod;
 623 }