FmpDevicePkg/FmpDxe/Dependency.c

   1 /** @file
   2   Supports Capsule Dependency Expression.
   3
   4   Copyright (c) 2020, Intel Corporation. All rights reserved.<BR>
   5
   6   SPDX-License-Identifier: BSD-2-Clause-Patent
   7
   8 **/
   9 #include "FmpDxe.h"
  10 #include "Dependency.h"
  11
  12 //
  13 // Define the initial size of the dependency expression evaluation stack
  14 //
  15 #define DEPEX_STACK_SIZE_INCREMENT  0x1000
  16
  17 //
  18 // Type of stack element
  19 //
  20 typedef enum {
  21   BooleanType,
  22   VersionType
  23 } ELEMENT_TYPE;
  24
  25 //
  26 // Value of stack element
  27 //
  28 typedef union {
  29   BOOLEAN   Boolean;
  30   UINT32    Version;
  31 } ELEMENT_VALUE;
  32
  33 //
  34 // Stack element used to evaluate dependency expressions
  35 //
  36 typedef struct {
  37   ELEMENT_VALUE Value;
  38   ELEMENT_TYPE  Type;
  39 } DEPEX_ELEMENT;
  40
  41 //
  42 // Global variable used to support dependency evaluation
  43 //
  44 UINTN                          mNumberOfFmpInstance = 0;
  45 EFI_FIRMWARE_IMAGE_DESCRIPTOR  **mFmpImageInfoBuf   = NULL;
  46
  47 //
  48 // Indicates the status of dependency check, default value is DEPENDENCIES_SATISFIED.
  49 //
  50 UINT8  mDependenciesCheckStatus = DEPENDENCIES_SATISFIED;
  51
  52 //
  53 // Global stack used to evaluate dependency expressions
  54 //
  55 DEPEX_ELEMENT  *mDepexEvaluationStack        = NULL;
  56 DEPEX_ELEMENT  *mDepexEvaluationStackEnd     = NULL;
  57 DEPEX_ELEMENT  *mDepexEvaluationStackPointer = NULL;
  58
  59 /**
  60   Grow size of the Depex stack
  61
  62   @retval EFI_SUCCESS           Stack successfully growed.
  63   @retval EFI_OUT_OF_RESOURCES  There is not enough system memory to grow the stack.
  64
  65 **/
  66 EFI_STATUS
  67 GrowDepexStack (
  68   VOID
  69   )
  70 {
  71   DEPEX_ELEMENT  *NewStack;
  72   UINTN          Size;
  73
  74   Size = DEPEX_STACK_SIZE_INCREMENT;
  75   if (mDepexEvaluationStack != NULL) {
  76     Size = Size + (mDepexEvaluationStackEnd - mDepexEvaluationStack);
  77   }
  78
  79   NewStack = AllocatePool (Size * sizeof (DEPEX_ELEMENT));
  80   if (NewStack == NULL) {
  81     return EFI_OUT_OF_RESOURCES;
  82   }
  83
  84   if (mDepexEvaluationStack != NULL) {
  85     //
  86     // Copy to Old Stack to the New Stack
  87     //
  88     CopyMem (
  89       NewStack,
  90       mDepexEvaluationStack,
  91       (mDepexEvaluationStackEnd - mDepexEvaluationStack) * sizeof (DEPEX_ELEMENT)
  92       );
  93
  94     //
  95     // Free The Old Stack
  96     //
  97     FreePool (mDepexEvaluationStack);
  98   }
  99
 100   //
 101   // Make the Stack pointer point to the old data in the new stack
 102   //
 103   mDepexEvaluationStackPointer = NewStack + (mDepexEvaluationStackPointer - mDepexEvaluationStack);
 104   mDepexEvaluationStack        = NewStack;
 105   mDepexEvaluationStackEnd     = NewStack + Size;
 106
 107   return EFI_SUCCESS;
 108 }
 109
 110 /**
 111   Push an element onto the Stack.
 112
 113   @param[in]  Value                  Value to push.
 114   @param[in]  Type                   Element Type
 115
 116   @retval EFI_SUCCESS            The value was pushed onto the stack.
 117   @retval EFI_OUT_OF_RESOURCES   There is not enough system memory to grow the stack.
 118   @retval EFI_INVALID_PARAMETER  Wrong stack element type.
 119
 120 **/
 121 EFI_STATUS
 122 Push (
 123   IN UINT32   Value,
 124   IN UINTN    Type
 125   )
 126 {
 127   EFI_STATUS      Status;
 128   DEPEX_ELEMENT   Element;
 129
 130   //
 131   // Check Type
 132   //
 133   if (Type != BooleanType && Type != VersionType) {
 134     return EFI_INVALID_PARAMETER;
 135   }
 136
 137   //
 138   // Check for a stack overflow condition
 139   //
 140   if (mDepexEvaluationStackPointer == mDepexEvaluationStackEnd) {
 141     //
 142     // Grow the stack
 143     //
 144     Status = GrowDepexStack ();
 145     if (EFI_ERROR (Status)) {
 146       return Status;
 147     }
 148   }
 149
 150   Element.Value.Version = Value;
 151   Element.Type = Type;
 152
 153   //
 154   // Push the item onto the stack
 155   //
 156   *mDepexEvaluationStackPointer = Element;
 157   mDepexEvaluationStackPointer++;
 158
 159   return EFI_SUCCESS;
 160 }
 161
 162
 163 /**
 164   Pop an element from the stack.
 165
 166   @param[out]  Element                Element to pop.
 167   @param[in]   Type                   Type of element.
 168
 169   @retval EFI_SUCCESS            The value was popped onto the stack.
 170   @retval EFI_ACCESS_DENIED      The pop operation underflowed the stack.
 171   @retval EFI_INVALID_PARAMETER  Type is mismatched.
 172
 173 **/
 174 EFI_STATUS
 175 Pop (
 176   OUT DEPEX_ELEMENT  *Element,
 177   IN  ELEMENT_TYPE   Type
 178   )
 179 {
 180   //
 181   // Check for a stack underflow condition
 182   //
 183   if (mDepexEvaluationStackPointer == mDepexEvaluationStack) {
 184     return EFI_ACCESS_DENIED;
 185   }
 186
 187   //
 188   // Pop the item off the stack
 189   //
 190   mDepexEvaluationStackPointer--;
 191   *Element = *mDepexEvaluationStackPointer;
 192   if ((*Element).Type != Type) {
 193     return EFI_INVALID_PARAMETER;
 194   }
 195   return EFI_SUCCESS;
 196 }
 197
 198 /**
 199   Evaluate the dependencies.
 200
 201   @param[in]   Dependencies        Dependency expressions.
 202   @param[in]   DependenciesSize    Size of Dependency expressions.
 203
 204   @retval TRUE           Dependency expressions evaluate to TRUE.
 205   @retval FALSE          Dependency expressions evaluate to FALSE.
 206
 207 **/
 208 BOOLEAN
 209 EvaluateDependencies (
 210   IN  CONST EFI_FIRMWARE_IMAGE_DEP *     Dependencies,
 211   IN  CONST UINTN                        DependenciesSize
 212   )
 213 {
 214   EFI_STATUS                        Status;
 215   UINT8                             *Iterator;
 216   UINT8                             Index;
 217   DEPEX_ELEMENT                     Element1;
 218   DEPEX_ELEMENT                     Element2;
 219   GUID                              ImageTypeId;
 220   UINT32                            Version;
 221
 222   if (Dependencies == NULL || DependenciesSize == 0) {
 223     return FALSE;
 224   }
 225
 226   //
 227   // Clean out memory leaks in Depex Boolean stack. Leaks are only caused by
 228   // incorrectly formed DEPEX expressions
 229   //
 230   mDepexEvaluationStackPointer = mDepexEvaluationStack;
 231
 232   Iterator = (UINT8 *) Dependencies->Dependencies;
 233   while (Iterator < (UINT8 *) Dependencies->Dependencies + DependenciesSize) {
 234     switch (*Iterator)
 235     {
 236     case EFI_FMP_DEP_PUSH_GUID:
 237       if (Iterator + sizeof (EFI_GUID) >= (UINT8 *) Dependencies->Dependencies + DependenciesSize) {
 238         Status = EFI_INVALID_PARAMETER;
 239         goto Error;
 240       }
 241
 242       CopyGuid (&ImageTypeId, (EFI_GUID *) (Iterator + 1));
 243       Iterator = Iterator + sizeof (EFI_GUID);
 244
 245       for (Index = 0; Index < mNumberOfFmpInstance; Index ++){
 246         if (mFmpImageInfoBuf[Index] == NULL) {
 247           continue;
 248         }
 249         if(CompareGuid (&mFmpImageInfoBuf[Index]->ImageTypeId, &ImageTypeId)){
 250           Status = Push (mFmpImageInfoBuf[Index]->Version, VersionType);
 251           if (EFI_ERROR (Status)) {
 252             goto Error;
 253           }
 254           break;
 255         }
 256       }
 257       if (Index == mNumberOfFmpInstance) {
 258         Status = EFI_NOT_FOUND;
 259         goto Error;
 260       }
 261       break;
 262     case EFI_FMP_DEP_PUSH_VERSION:
 263       if (Iterator + sizeof (UINT32) >= (UINT8 *) Dependencies->Dependencies + DependenciesSize ) {
 264         Status = EFI_INVALID_PARAMETER;
 265         goto Error;
 266       }
 267
 268       Version = *(UINT32 *) (Iterator + 1);
 269       Status = Push (Version, VersionType);
 270       if (EFI_ERROR (Status)) {
 271         goto Error;
 272       }
 273       Iterator = Iterator + sizeof (UINT32);
 274       break;
 275     case EFI_FMP_DEP_VERSION_STR:
 276       Iterator += AsciiStrnLenS ((CHAR8 *) Iterator, DependenciesSize - (Iterator - Dependencies->Dependencies));
 277       break;
 278     case EFI_FMP_DEP_AND:
 279       Status = Pop (&Element1, BooleanType);
 280       if (EFI_ERROR (Status)) {
 281         goto Error;
 282       }
 283       Status = Pop (&Element2, BooleanType);
 284       if (EFI_ERROR (Status)) {
 285         goto Error;
 286       }
 287       Status = Push (Element1.Value.Boolean & Element2.Value.Boolean, BooleanType);
 288       if (EFI_ERROR (Status)) {
 289         goto Error;
 290       }
 291       break;
 292     case EFI_FMP_DEP_OR:
 293       Status = Pop (&Element1, BooleanType);
 294       if (EFI_ERROR (Status)) {
 295         goto Error;
 296       }
 297       Status = Pop(&Element2, BooleanType);
 298       if (EFI_ERROR (Status)) {
 299         goto Error;
 300       }
 301       Status = Push (Element1.Value.Boolean | Element2.Value.Boolean, BooleanType);
 302       if (EFI_ERROR (Status)) {
 303         goto Error;
 304       }
 305       break;
 306     case EFI_FMP_DEP_NOT:
 307       Status = Pop (&Element1, BooleanType);
 308       if (EFI_ERROR (Status)) {
 309         goto Error;
 310       }
 311       Status = Push (!(Element1.Value.Boolean), BooleanType);
 312       if (EFI_ERROR (Status)) {
 313         goto Error;
 314       }
 315       break;
 316     case EFI_FMP_DEP_TRUE:
 317       Status = Push (TRUE, BooleanType);
 318       if (EFI_ERROR (Status)) {
 319         goto Error;
 320       }
 321       break;
 322     case EFI_FMP_DEP_FALSE:
 323       Status = Push (FALSE, BooleanType);
 324       if (EFI_ERROR (Status)) {
 325         goto Error;
 326       }
 327       break;
 328     case EFI_FMP_DEP_EQ:
 329       Status = Pop (&Element1, VersionType);
 330       if (EFI_ERROR (Status)) {
 331         goto Error;
 332       }
 333       Status = Pop (&Element2, VersionType);
 334       if (EFI_ERROR (Status)) {
 335         goto Error;
 336       }
 337       Status = (Element1.Value.Version == Element2.Value.Version) ? Push (TRUE, BooleanType) : Push (FALSE, BooleanType);
 338       if (EFI_ERROR (Status)) {
 339         goto Error;
 340       }
 341       break;
 342     case EFI_FMP_DEP_GT:
 343       Status = Pop (&Element1, VersionType);
 344       if (EFI_ERROR (Status)) {
 345         goto Error;
 346       }
 347       Status = Pop (&Element2, VersionType);
 348       if (EFI_ERROR (Status)) {
 349         goto Error;
 350       }
 351       Status = (Element1.Value.Version >  Element2.Value.Version) ? Push (TRUE, BooleanType) : Push (FALSE, BooleanType);
 352       if (EFI_ERROR (Status)) {
 353         goto Error;
 354       }
 355       break;
 356     case EFI_FMP_DEP_GTE:
 357       Status = Pop (&Element1, VersionType);
 358       if (EFI_ERROR (Status)) {
 359         goto Error;
 360       }
 361       Status = Pop (&Element2, VersionType);
 362       if (EFI_ERROR (Status)) {
 363         goto Error;
 364       }
 365       Status = (Element1.Value.Version >= Element2.Value.Version) ? Push (TRUE, BooleanType) : Push (FALSE, BooleanType);
 366       if (EFI_ERROR (Status)) {
 367         goto Error;
 368       }
 369       break;
 370     case EFI_FMP_DEP_LT:
 371       Status = Pop (&Element1, VersionType);
 372       if (EFI_ERROR (Status)) {
 373         goto Error;
 374       }
 375       Status = Pop (&Element2, VersionType);
 376       if (EFI_ERROR (Status)) {
 377         goto Error;
 378       }
 379       Status = (Element1.Value.Version <  Element2.Value.Version) ? Push (TRUE, BooleanType) : Push (FALSE, BooleanType);
 380       if (EFI_ERROR (Status)) {
 381         goto Error;
 382       }
 383       break;
 384     case EFI_FMP_DEP_LTE:
 385       Status = Pop (&Element1, VersionType);
 386       if (EFI_ERROR (Status)) {
 387         goto Error;
 388       }
 389       Status = Pop (&Element2, VersionType);
 390       if (EFI_ERROR (Status)) {
 391         goto Error;
 392       }
 393       Status = (Element1.Value.Version <= Element2.Value.Version) ? Push (TRUE, BooleanType) : Push (FALSE, BooleanType);
 394       if (EFI_ERROR (Status)) {
 395         goto Error;
 396       }
 397       break;
 398     case EFI_FMP_DEP_END:
 399       Status = Pop (&Element1, BooleanType);
 400       if (EFI_ERROR (Status)) {
 401         goto Error;
 402       }
 403       return Element1.Value.Boolean;
 404     default:
 405       Status = EFI_INVALID_PARAMETER;
 406       goto Error;
 407     }
 408     Iterator++;
 409   }
 410
 411 Error:
 412
 413   DEBUG ((DEBUG_ERROR, "FmpDxe(%s): EvaluateDependencies() - RESULT = FALSE (Status = %r)\n", mImageIdName, Status));
 414   return FALSE;
 415 }
 416
 417 /**
 418   Validate the dependency expression and output its size.
 419
 420   @param[in]   ImageDepex      Pointer to the EFI_FIRMWARE_IMAGE_DEP.
 421   @param[in]   MaxDepexSize    Max size of the dependency.
 422   @param[out]  DepexSize       Size of dependency.
 423
 424   @retval TRUE           The capsule is valid.
 425   @retval FALSE          The capsule is invalid.
 426
 427 **/
 428 BOOLEAN
 429 ValidateImageDepex (
 430   IN  EFI_FIRMWARE_IMAGE_DEP             *ImageDepex,
 431   IN  CONST UINTN                        MaxDepexSize,
 432   OUT UINT32                             *DepexSize
 433   )
 434 {
 435   UINT8  *Depex;
 436
 437   *DepexSize = 0;
 438   Depex = ImageDepex->Dependencies;
 439   while (Depex < ImageDepex->Dependencies + MaxDepexSize) {
 440     switch (*Depex)
 441     {
 442     case EFI_FMP_DEP_PUSH_GUID:
 443       Depex += sizeof (EFI_GUID) + 1;
 444       break;
 445     case EFI_FMP_DEP_PUSH_VERSION:
 446       Depex += sizeof (UINT32) + 1;
 447       break;
 448     case EFI_FMP_DEP_VERSION_STR:
 449       Depex += AsciiStrnLenS ((CHAR8 *) Depex, ImageDepex->Dependencies + MaxDepexSize - Depex) + 1;
 450       break;
 451     case EFI_FMP_DEP_AND:
 452     case EFI_FMP_DEP_OR:
 453     case EFI_FMP_DEP_NOT:
 454     case EFI_FMP_DEP_TRUE:
 455     case EFI_FMP_DEP_FALSE:
 456     case EFI_FMP_DEP_EQ:
 457     case EFI_FMP_DEP_GT:
 458     case EFI_FMP_DEP_GTE:
 459     case EFI_FMP_DEP_LT:
 460     case EFI_FMP_DEP_LTE:
 461       Depex += 1;
 462       break;
 463     case EFI_FMP_DEP_END:
 464       Depex += 1;
 465       *DepexSize = (UINT32)(Depex - ImageDepex->Dependencies);
 466       return TRUE;
 467     default:
 468       return FALSE;
 469     }
 470   }
 471
 472   return FALSE;
 473 }
 474
 475
 476 /**
 477   Get the size of dependencies. Assume the dependencies is validated before
 478   calling this function.
 479
 480   @param[in]   Dependencies    Pointer to the EFI_FIRMWARE_IMAGE_DEP.
 481
 482   @retval  The size of dependencies.
 483
 484 **/
 485 UINTN
 486 GetDepexSize (
 487   IN CONST EFI_FIRMWARE_IMAGE_DEP  *Dependencies
 488   )
 489 {
 490   UINTN Index;
 491
 492   if (Dependencies == NULL) {
 493     return 0;
 494   }
 495
 496   Index = 0;
 497   while (Dependencies->Dependencies[Index] != EFI_FMP_DEP_END) {
 498     Index ++;
 499   }
 500
 501   return Index + 1;
 502 }
 503
 504 /**
 505   Check dependency for firmware update.
 506
 507   @param[in]   ImageTypeId         Image Type Id.
 508   @param[in]   Version             New version.
 509   @param[in]   Dependencies        The dependencies.
 510   @param[in]   DependenciesSize    Size of the dependencies
 511   @param[out]  IsSatisfied         Indicate the dependencies is satisfied or not.
 512
 513   @retval  EFI_SUCCESS             Dependency Evaluation is successful.
 514   @retval  Others                  Dependency Evaluation fails with unexpected error.
 515
 516 **/
 517 EFI_STATUS
 518 EvaluateImageDependencies (
 519   IN CONST EFI_GUID                ImageTypeId,
 520   IN CONST UINT32                  Version,
 521   IN CONST EFI_FIRMWARE_IMAGE_DEP  *Dependencies,
 522   IN CONST UINT32                  DependenciesSize,
 523   OUT BOOLEAN                      *IsSatisfied
 524   )
 525 {
 526   EFI_STATUS                        Status;
 527   EFI_HANDLE                        *HandleBuffer;
 528   UINTN                             Index;
 529   EFI_FIRMWARE_MANAGEMENT_PROTOCOL  *Fmp;
 530   UINTN                             ImageInfoSize;
 531   UINT32                            FmpImageInfoDescriptorVer;
 532   UINT8                             FmpImageInfoCount;
 533   UINTN                             DescriptorSize;
 534   UINT32                            PackageVersion;
 535   CHAR16                            *PackageVersionName;
 536   UINTN                             DepexSize;
 537
 538   *IsSatisfied       = TRUE;
 539   PackageVersionName = NULL;
 540
 541   //
 542   // Get ImageDescriptors of all FMP instances, and archive them for depex evaluation.
 543   //
 544   Status = gBS->LocateHandleBuffer (
 545                 ByProtocol,
 546                 &gEfiFirmwareManagementProtocolGuid,
 547                 NULL,
 548                 &mNumberOfFmpInstance,
 549                 &HandleBuffer
 550                 );
 551   if (EFI_ERROR (Status)) {
 552     return EFI_ABORTED;
 553   }
 554
 555   mFmpImageInfoBuf = AllocatePool (sizeof(EFI_FIRMWARE_IMAGE_DESCRIPTOR *) * mNumberOfFmpInstance);
 556   if (mFmpImageInfoBuf == NULL) {
 557     return EFI_OUT_OF_RESOURCES;
 558   }
 559
 560   for (Index = 0; Index < mNumberOfFmpInstance; Index ++) {
 561     Status = gBS->HandleProtocol (
 562                     HandleBuffer[Index],
 563                     &gEfiFirmwareManagementProtocolGuid,
 564                     (VOID **) &Fmp
 565                     );
 566     if (EFI_ERROR(Status)) {
 567       continue;
 568     }
 569
 570     ImageInfoSize = 0;
 571     Status = Fmp->GetImageInfo (
 572                     Fmp,
 573                     &ImageInfoSize,
 574                     NULL,
 575                     NULL,
 576                     NULL,
 577                     NULL,
 578                     NULL,
 579                     NULL
 580                     );
 581     if (Status != EFI_BUFFER_TOO_SMALL) {
 582       continue;
 583     }
 584
 585     mFmpImageInfoBuf[Index] = AllocateZeroPool (ImageInfoSize);
 586     if (mFmpImageInfoBuf[Index] == NULL) {
 587       continue;
 588     }
 589
 590     Status = Fmp->GetImageInfo (
 591                     Fmp,
 592                     &ImageInfoSize,               // ImageInfoSize
 593                     mFmpImageInfoBuf[Index],      // ImageInfo
 594                     &FmpImageInfoDescriptorVer,   // DescriptorVersion
 595                     &FmpImageInfoCount,           // DescriptorCount
 596                     &DescriptorSize,              // DescriptorSize
 597                     &PackageVersion,              // PackageVersion
 598                     &PackageVersionName           // PackageVersionName
 599                     );
 600     if (EFI_ERROR(Status)) {
 601       FreePool (mFmpImageInfoBuf[Index]);
 602       mFmpImageInfoBuf[Index] = NULL;
 603       continue;
 604     }
 605
 606     if (PackageVersionName != NULL) {
 607       FreePool (PackageVersionName);
 608       PackageVersionName = NULL;
 609     }
 610   }
 611
 612   //
 613   // Step 1 - Evaluate firmware image's depex, against the version of other Fmp instances.
 614   //
 615   if (Dependencies != NULL) {
 616     *IsSatisfied = EvaluateDependencies (Dependencies, DependenciesSize);
 617   }
 618
 619   if (!*IsSatisfied) {
 620     goto cleanup;
 621   }
 622
 623   //
 624   // Step 2 - Evaluate the depex of all other Fmp instances, against the new version in
 625   // the firmware image.
 626   //
 627
 628   //
 629   // Update the new version to mFmpImageInfoBuf.
 630   //
 631   for (Index = 0; Index < mNumberOfFmpInstance; Index ++) {
 632     if (mFmpImageInfoBuf[Index] != NULL) {
 633       if (CompareGuid (&ImageTypeId, &mFmpImageInfoBuf[Index]->ImageTypeId)) {
 634         mFmpImageInfoBuf[Index]->Version = Version;
 635         break;
 636       }
 637     }
 638   }
 639
 640   //
 641   // Evaluate the Dependencies one by one.
 642   //
 643   for (Index = 0; Index < mNumberOfFmpInstance; Index ++) {
 644     if (mFmpImageInfoBuf[Index] != NULL) {
 645       //
 646       // Skip the Fmp instance to be "SetImage".
 647       //
 648       if (CompareGuid (&ImageTypeId, &mFmpImageInfoBuf[Index]->ImageTypeId)) {
 649         continue;
 650       }
 651       if ((mFmpImageInfoBuf[Index]->AttributesSupported & IMAGE_ATTRIBUTE_DEPENDENCY) &&
 652            mFmpImageInfoBuf[Index]->Dependencies != NULL) {
 653         //
 654         // Get the size of depex.
 655         // Assume that the dependencies in EFI_FIRMWARE_IMAGE_DESCRIPTOR is validated when PopulateDescriptor().
 656         //
 657         DepexSize = GetDepexSize (mFmpImageInfoBuf[Index]->Dependencies);
 658         if (DepexSize > 0) {
 659           *IsSatisfied = EvaluateDependencies (mFmpImageInfoBuf[Index]->Dependencies, DepexSize);
 660           if (!*IsSatisfied) {
 661             break;
 662           }
 663         }
 664       }
 665     }
 666   }
 667
 668 cleanup:
 669   if (mFmpImageInfoBuf != NULL) {
 670     for (Index = 0; Index < mNumberOfFmpInstance; Index ++) {
 671       if (mFmpImageInfoBuf[Index] != NULL) {
 672         FreePool (mFmpImageInfoBuf[Index]);
 673       }
 674     }
 675     FreePool (mFmpImageInfoBuf);
 676   }
 677
 678   return EFI_SUCCESS;
 679 }