A SPaT (Signal Phase and Timing) message describes for each lane the current phase at a signalized intersection together with an estimate of the residual time of that phase. Accurate SPaT messages can be used to construct a speed profile for a vehicle that reduces its fuel consumption as it approaches or leaves an intersection. This paper presents SPaT estimation algorithms at an intersection with a semi-actuated signal, using real-time signal phase measurements. The algorithms are evaluated using high-resolution data from two intersections in Montgomery County, MD. The algorithms can be readily implemented at signal controllers. The study supports three findings. First, real-time information dramatically improves the accuracy of the prediction of the residual time compared with prediction based on historical data alone. Second, as time increases the prediction of the residual time may increase or decrease. Third, as drivers differently weight errors in predicting `end of green' and `end of red', drivers on two different approaches may prefer different estimates of the residual time of the same phase.